Pollard's kangaroo algorithm
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಖ್ಯೆ ಸಿದ್ಧಾಂತ ಮತ್ತು ಕಂಪ್ಯೂಟೇಶನಲ್ ಬೀಜಗಣಿತದಲ್ಲಿ, ಪೊಲಾರ್ಡ್ನ ಕಂಗಾರೂ ಅಲ್ಗಾರಿದಮ್ (ಪೊಲಾರ್ಡ್ನ ಲ್ಯಾಂಬ್ಡಾ ಅಲ್ಗಾರಿದಮ್, ಕೆಳಗೆ ಹೆಸರಿಸುವುದನ್ನು ನೋಡಿ) ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಒಂದು ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ಅನ್ನು 1978ರಲ್ಲಿ ಸಂಖ್ಯಾ ಸಿದ್ಧಾಂತಿ ಜಾನ್ ಎಮ್. ಪೊಲಾರ್ಡ್ ಅವರು ಅದೇ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಅವರ ಪ್ರಸಿದ್ಧವಾದ ಪೊಲಾರ್ಡ್ ಅವರ ರೋ ಅಲ್ಗಾರಿದಮ್ನ ಅದೇ ಪ್ರಬಂಧದಲ್ಲಿ ಪರಿಚಯಿಸಿದರು. ಪೊಲಾರ್ಡ್ ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಸಮಸ್ಯೆಗೆ ತನ್ನ ಅಲ್ಗಾರಿದಮ್ನ ಅನ್ವಯವನ್ನು ಮಾಡ್ಯುಲೋ a ಪ್ರೈಮ್ p ಘಟಕಗಳ ಗುಣಾಕಾರ ಗುಂಪಿನಲ್ಲಿ ವಿವರಿಸಿದ್ದರೂ, ಇದು ವಾಸ್ತವವಾಗಿ ಸಾಮಾನ್ಯ ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ-ಇದು ಯಾವುದೇ ಸೀಮಿತ ಆವರ್ತಕ ಗುಂಪಿನಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಅಂಶದಿಂದ ಉತ್ಪತ್ತಿಯಾಗುವ ಕ್ರಮದ ಒಂದು ಸೀಮಿತ ಆವರ್ತಕ ಗುಂಪು ಎಂದು ಭಾವಿಸೋಣ, ಮತ್ತು ನಾವು ಮೂಲಕ್ಕೆ ಅಂಶದ ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಒಬ್ಬರು ಅಂತಹದ್ದನ್ನು ಬಯಸುತ್ತಾರೆ. ಲ್ಯಾಂಬ್ಡಾ ಅಲ್ಗಾರಿದಮ್ ಕೆಲವು ಮಧ್ಯಂತರಗಳಲ್ಲಿ ಹುಡುಕಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಮತ್ತು ಅನ್ನು ಹೊಂದಿಸುವ ಮೂಲಕ ಸಂಭವನೀಯ ಲಾಗರಿಥಮ್ಗಳ ಸಂಪೂರ್ಣ ಶ್ರೇಣಿಯನ್ನು ಹುಡುಕಬಹುದು. 1. ಸ್ಥೂಲವಾಗಿ ಸರಾಸರಿ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳ ಗುಂಪನ್ನು ಆಯ್ಕೆ ಮಾಡಿ ಮತ್ತು ಸೂಡೊರಾಂಡಮ್ ನಕ್ಷೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿ. 2. ಒಂದು ಪೂರ್ಣಾಂಕವನ್ನು ಆಯ್ಕೆ ಮಾಡಿ ಮತ್ತು 3ರ ಪ್ರಕಾರ ಗುಂಪು ಅಂಶಗಳ ಅನುಕ್ರಮವನ್ನು ಲೆಕ್ಕ ಹಾಕಿ. ಇದನ್ನು ಗಮನಿಸಿಃ 4. ಗುಂಪಿನ ಅಂಶಗಳ ಎರಡನೇ ಅನುಕ್ರಮವನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಲು ಪ್ರಾರಂಭಿಸಿಃ ಮತ್ತು ಅದಕ್ಕೆ ಅನುಗುಣವಾದ ಪೂರ್ಣಾಂಕಗಳ ಅನುಕ್ರಮವುಃ. ಇದನ್ನು ಗಮನಿಸಿಃ 5. ಈ ಕೆಳಗಿನ ಷರತ್ತುಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಒಂದನ್ನು ಯಾವಾಗ ಪೂರೈಸಲಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದನ್ನು ನಿಲ್ಲಿಸಿಃ ಎ) ಕೆಲವರಿಗೆ. ಅನುಕ್ರಮಗಳು ಮತ್ತು "ಘರ್ಷಣೆ" ಈ ರೀತಿಯಲ್ಲಿ ಇದ್ದರೆ, ನಾವು ಹೊಂದಿದ್ದೇವೆಃ ಮತ್ತು ಆದ್ದರಿಂದ ನಾವು ಮುಗಿಸಿದ್ದೇವೆ. ಬಿ). ಇದು ಸಂಭವಿಸಿದಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ವಿಫಲವಾಗಿದೆ. ಮತ್ತು/ಅಥವಾ ಆಯ್ಕೆಯನ್ನು ಬದಲಾಯಿಸುವ ಮೂಲಕ ನಂತರದ ಪ್ರಯತ್ನಗಳನ್ನು ಮಾಡಬಹುದು. ಪೋಲಾರ್ಡ್ ಸಂಕೀರ್ಣತೆಯು ಅಲ್ಗಾರಿದಮ್ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ನೀಡುತ್ತದೆ, ಇದು ಊಹೆಯ ಆಧಾರದ ಮೇಲೆ ಸಂಭವನೀಯ ವಾದವನ್ನು ಬಳಸುತ್ತದೆ. ಬಿಟ್ಗಳನ್ನು ಬಳಸಿ ಪ್ರತಿನಿಧಿಸಬಹುದಾದ್ದರಿಂದ, ಇದು ಸಮಸ್ಯೆಯ ಗಾತ್ರದಲ್ಲಿ ಘಾತೀಯವಾಗಿದೆ (ಆದರೂ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುವ ಕ್ಷುಲ್ಲಕ ಬ್ರೂಟ್-ಫೋರ್ಸ್ ಅಲ್ಗಾರಿದಮ್ಗಿಂತ ಗಮನಾರ್ಹ ಸುಧಾರಣೆಯಾಗಿದೆ). ಸಬ್ಎಕ್ಸ್ಪೊನೆನ್ಷಿಯಲ್ ಟೈಮ್ ಡಿಸ್ಕ್ರೀಟ್ ಲಾಗರಿಥಮ್ ಅಲ್ಗಾರಿದಮ್ನ ಉದಾಹರಣೆಗಾಗಿ, ಇಂಡೆಕ್ಸ್ ಕ್ಯಾಲ್ಕುಲಸ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೋಡಿ. ಹೆಸರಿಡುವುದು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಎರಡು ಹೆಸರುಗಳಿಂದ ಕರೆಯಲಾಗುತ್ತದೆ. ಮೊದಲನೆಯದು "ಪೊಲಾರ್ಡ್ಸ್ ಕಂಗಾರೂ ಅಲ್ಗಾರಿದಮ್". ಈ ಹೆಸರು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುವ ಕಾಗದದಲ್ಲಿ ಬಳಸಿದ ಸಾದೃಶ್ಯವನ್ನು ಉಲ್ಲೇಖಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಾಡು ಕಂಗಾರುವನ್ನು ಬಲೆಗೆ ಬೀಳಿಸಲು ಪಳಗಿಸಿದ ಕಂಗಾರುವನ್ನು ಬಳಸುವ ಪರಿಭಾಷೆಯಲ್ಲಿ ವಿವರಿಸಲಾಗಿದೆ. ಈ ಸಾದೃಶ್ಯವು ಸೈಂಟಿಫಿಕ್ ಅಮೇರಿಕನ್ನ ಅದೇ ಸಂಚಿಕೆಯಲ್ಲಿ ಆರ್. ಎಸ್. ಎ. ಸಾರ್ವಜನಿಕ ಕೀ ಗುಪ್ತ ಲಿಪಿ ವ್ಯವಸ್ಥೆಯ ವಿವರಣೆಯಾಗಿ ಪ್ರಕಟವಾದ "ಆಕರ್ಷಕ" ಲೇಖನದಿಂದ ಸ್ಫೂರ್ತಿ ಪಡೆದಿದೆ ಎಂದು ಪೊಲಾರ್ಡ್ ವಿವರಿಸಿದ್ದಾರೆ. ಈ ಲೇಖನವು ಒಂದು ಪ್ರಯೋಗವನ್ನು ವಿವರಿಸಿದೆ, ಇದರಲ್ಲಿ "ವಿವಿಧ ವೇಗಗಳಲ್ಲಿ ಆಮ್ಲಜನಕದ ಬಳಕೆಯ ದೃಷ್ಟಿಯಿಂದ ಅಳೆಯಲಾದ ಕಂಗಾರೂಗಳ ಚಲನಶೀಲತೆಯ ಶಕ್ತಿಯುತ ವೆಚ್ಚವನ್ನು ಟ್ರೆಡ್ಮಿಲ್ನಲ್ಲಿ ಕಂಗಾರೂಗಳನ್ನು ಇರಿಸುವ ಮೂಲಕ ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ". ಎರಡನೆಯದು "ಪೊಲಾರ್ಡ್ಸ್ ಲ್ಯಾಂಬ್ಡಾ ಅಲ್ಗಾರಿದಮ್". ಪೋಲಾರ್ಡ್ರ ಪ್ರತ್ಯೇಕ ಲಾಗರಿಥಮ್ ಅಲ್ಗಾರಿದಮ್ಗಳ ಮತ್ತೊಂದು ಹೆಸರಿನಂತೆಯೇ, ಪೋಲಾರ್ಡ್ರ ರೋ ಅಲ್ಗಾರಿದಮ್, ಈ ಹೆಸರು ಅಲ್ಗಾರಿದಮ್ನ ದೃಶ್ಯೀಕರಣ ಮತ್ತು ಗ್ರೀಕ್ ಅಕ್ಷರ ಲ್ಯಾಂಬ್ಡಾ (λ) ನಡುವಿನ ಹೋಲಿಕೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಲ್ಯಾಂಬ್ಡಾ ಅಕ್ಷರದ ಚಿಕ್ಕ ಸ್ಟ್ರೋಕ್ ಅನುಕ್ರಮಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ, ಏಕೆಂದರೆ ಇದು ಬಿ ಸ್ಥಾನದಿಂದ x ನ ಬಲಕ್ಕೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ. ಅಂತೆಯೇ, ಉದ್ದವಾದ ಹೊಡೆತವು ಅನುಕ್ರಮಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ, ಇದು ಮೊದಲ ಅನುಕ್ರಮಕ್ಕೆ "ಡಿಕ್ಕಿ ಹೊಡೆಯುತ್ತದೆ" (ಲ್ಯಾಂಬ್ಡಾ ಛೇದಿಸುವ ಹೊಡೆತಗಳಂತೆಯೇ) ಮತ್ತು ನಂತರ ಅದನ್ನು ಅನುಸರಿಸುತ್ತದೆ. ಪೊಲಾರ್ಡ್ "ಕಂಗಾರೂ ಅಲ್ಗಾರಿದಮ್" ಎಂಬ ಹೆಸರಿಗೆ ಆದ್ಯತೆಯನ್ನು ವ್ಯಕ್ತಪಡಿಸಿದ್ದಾರೆ, ಏಕೆಂದರೆ ಇದು ಅವರ ರೋ ಅಲ್ಗಾರಿದಮ್ನ ಕೆಲವು ಸಮಾನಾಂತರ ಆವೃತ್ತಿಗಳೊಂದಿಗೆ ಗೊಂದಲವನ್ನು ತಪ್ಪಿಸುತ್ತದೆ, ಇದನ್ನು "ಲ್ಯಾಂಬ್ಡಾ ಅಲ್ಗಾರಿದಮ್" ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಡೈನ್ಕಿನ್ನ ಕಾರ್ಡ್ ಟ್ರಿಕ್ ಕ್ರುಸ್ಕಲ್ ಕೌಂಟ್ ರೇನ್ಬೋ ಟೇಬಲ್ ರೆಫರೆನ್ಸಸ್ ಅನ್ನು ಸಹ ನೋಡಿ ಮತ್ತಷ್ಟು ಓದುವಿಕೆ ಸಂಖ್ಯೆ ಸೈದ್ಧಾಂತಿಕ ಕ್ರಮಾವಳಿಗಳು ಕಂಪ್ಯೂಟರ್ ಬೀಜಗಣಿತ ಲಾಗರಿಥಮ್ಸ್