Barrett reduction
ಮಾಡ್ಯುಲರ್ ಅಂಕಗಣಿತದಲ್ಲಿ, ಬ್ಯಾರೆಟ್ ರಿಡಕ್ಷನ್ ಎಂಬುದು 1986ರಲ್ಲಿ ಪಿ. ಡಿ. ಅವರು ಪರಿಚಯಿಸಿದ ರಿಡಕ್ಷನ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಬ್ಯಾರೆಟ್. ವೇಗವಾದ ವಿಭಜನೆಯ ಕ್ರಮಾವಳಿಗಳನ್ನು ಬಳಸುವುದು ಗಣನೆಯ ನಿಷ್ಕಪಟ ವಿಧಾನವಾಗಿದೆ. ಬ್ಯಾರೆಟ್ ಕಡಿತವು ಈ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಸ್ಥಿರವೆಂದು ಭಾವಿಸಿ ಅತ್ಯುತ್ತಮವಾಗಿಸಲು ವಿನ್ಯಾಸಗೊಳಿಸಲಾದ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ, ಮತ್ತು ವಿಭಾಗಗಳನ್ನು ಗುಣಾಕಾರಗಳಿಂದ ಬದಲಾಯಿಸುತ್ತದೆ. ಐತಿಹಾಸಿಕವಾಗಿ, ಮೌಲ್ಯಗಳಿಗಾಗಿ, ಪೂರ್ಣ ಉತ್ಪನ್ನಕ್ಕೆ ಬ್ಯಾರೆಟ್ ಕಡಿತವನ್ನು ಅನ್ವಯಿಸುವ ಮೂಲಕ ಲೆಕ್ಕ ಹಾಕಲಾಗುತ್ತದೆ. ಇತ್ತೀಚೆಗೆ, ನಾವು ಒಪೆರಾಂಡ್ಗಳಲ್ಲಿ ಒಂದರ ಮೇಲೆ ಪೂರ್ವ ಗಣನೆಯನ್ನು ಮಾಡಬಹುದಾದರೆ ಪೂರ್ಣ ಉತ್ಪನ್ನವು ಅನಗತ್ಯವಾಗಿದೆ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಸಾಮಾನ್ಯ ಕಲ್ಪನೆ ನಾವು ಒಂದು ಕಾರ್ಯವನ್ನು ಪೂರ್ಣಾಂಕ ಅಂದಾಜು ಎಂದು ಕರೆಯುತ್ತೇವೆ. ಮಾಡ್ಯುಲಸ್ ಮತ್ತು ಪೂರ್ಣಾಂಕ ಅಂದಾಜುಗಾಗಿ, ನಾವು ಇದನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ. ಸಾಮಾನ್ಯ ಆಯ್ಕೆಗಳೆಂದರೆ ನೆಲ, ಸೀಲಿಂಗ್ ಮತ್ತು ರೌಂಡಿಂಗ್ ಕಾರ್ಯಗಳು. ಸಾಮಾನ್ಯವಾಗಿ, ಬ್ಯಾರೆಟ್ ಗುಣಾಕಾರವು ಎರಡು ಪೂರ್ಣಾಂಕದ ಅಂದಾಜುಗಳನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುವ ಮೂಲಕ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಅಲ್ಲಿ ಒಂದು ಸ್ಥಿರ ಸ್ಥಿರಾಂಕ, ಸಾಮಾನ್ಯವಾಗಿ 2 ರ ಶಕ್ತಿಯಂತೆ ಸಮಂಜಸವಾದ ಹತ್ತಿರದ ಅಂದಾಜುಗಳನ್ನು ಲೆಕ್ಕ ಹಾಕುತ್ತದೆ, ಇದರಿಂದಾಗಿ ಗುಣಾಕಾರ ಮತ್ತು ವಿಭಜನೆಯನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಬಹುದು. ಈ ಪ್ರಕರಣವನ್ನು ಪಿ. ಡಿ. ಮಂಡಿಸಿದರು. ಫ್ಲೋರ್-ಫಂಕ್ಷನ್ ಕೇಸ್ಗಾಗಿ ಬ್ಯಾರೆಟ್. ಸಾಮಾನ್ಯ ಪ್ರಕರಣವನ್ನು ಎನ್. ಟಿ. ಎಲ್. ನಲ್ಲಿ ಕಾಣಬಹುದು. ಪೂರ್ಣಾಂಕ ಅಂದಾಜು ನೋಟ ಮತ್ತು ಮಾಂಟ್ಗೊಮೆರಿ ಗುಣಾಕಾರ ಮತ್ತು ಬ್ಯಾರೆಟ್ ಗುಣಾಕಾರದ ನಡುವಿನ ಸಂಬಂಧವನ್ನು ಹ್ಯಾನೋ ಬೆಕರ್, ವಿನ್ಸೆಂಟ್ ಹ್ವಾಂಗ್, ಮ್ಯಾಥಿಯಸ್ ಜೆ. ಕನ್ನ್ವಿಷರ್, ಬೋ-ಯಿನ್ ಯಾಂಗ್ ಮತ್ತು ಶಾಂಗ್-ಯಿ ಯಾಂಗ್ ಕಂಡುಹಿಡಿದರು. ಏಕ-ಪದ ಬ್ಯಾರೆಟ್ ರಿಡಕ್ಷನ್ ಬ್ಯಾರೆಟ್ ಅನ್ನು ಆರಂಭದಲ್ಲಿ ಯಂತ್ರ ಪದಗಳಿಗೆ ಮೌಲ್ಯಗಳು ಹೊಂದಿಕೊಂಡಾಗ ಮೇಲಿನ ಅಲ್ಗಾರಿದಮ್ನ ಪೂರ್ಣಾಂಕ ಆವೃತ್ತಿಯೆಂದು ಪರಿಗಣಿಸಲಾಗಿತ್ತು. ಮತ್ತು ನೊಂದಿಗೆ ಫ್ಲೋರ್-ಫಂಕ್ಷನ್ ಕೇಸ್ನ ಕಲ್ಪನೆಯನ್ನು ನಾವು ವಿವರಿಸುತ್ತೇವೆ. ಸಹಿ ಮಾಡದ ಪೂರ್ಣಾಂಕಗಳಿಗೆ ಲೆಕ್ಕ ಹಾಕುವಾಗ, ಈ ಕೆಳಗಿನ ವಿಭಾಗವನ್ನು ಬಳಸುವುದು ಸ್ಪಷ್ಟವಾದ ಸಾದೃಶ್ಯವಾಗಿದೆಃ ಫಂಕ್ ರಿಡ್ಯೂಸ್ (ಎ ಯುಯಿನ್ಟ್) ಯುಯಿನ್ಟ್ {q: = a/n// ಡಿವಿಷನ್ ಸೂಚ್ಯವಾಗಿ ಫಲಿತಾಂಶದ ನೆಲವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ವಿಭಾಗವು ದುಬಾರಿಯಾಗಬಹುದು ಮತ್ತು ಗೂಢಲಿಪೀಕರಣದ ಸೆಟ್ಟಿಂಗ್ಗಳಲ್ಲಿ, ಕೆಲವು ಸಿಪಿಯುಗಳ ಮೇಲೆ ನಿರಂತರ-ಸಮಯದ ಸೂಚನೆಯಾಗಿರದೇ ಇರಬಹುದು, ಇದು ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಸಮಯದ ದಾಳಿಗೆ ಒಳಪಡಿಸುತ್ತದೆ. ಹೀಗಾಗಿ ಬ್ಯಾರೆಟ್ ಕಡಿತವು ಮೌಲ್ಯದೊಂದಿಗೆ ಅಂದಾಜು ಮಾಡುತ್ತದೆ ಏಕೆಂದರೆ ವಿಭಜನೆಯು ಕೇವಲ ಬಲ-ಶಿಫ್ಟ್ ಆಗಿದೆ, ಮತ್ತು ಆದ್ದರಿಂದ ಇದು ಅಗ್ಗವಾಗಿದೆ. ಕೊಟ್ಟಿರುವ ಪರಿಗಣನೆಯ ಅತ್ಯುತ್ತಮ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕಹಾಕಲುಃ ಒಂದು ಪೂರ್ಣಾಂಕವಾಗಲು, ನಾವು ಹೇಗಾದರೂ ಪೂರ್ಣಾಂಕವನ್ನು ಮಾಡಬೇಕಾಗುತ್ತದೆ. ಹತ್ತಿರದ ಪೂರ್ಣಾಂಕಕ್ಕೆ ಪೂರ್ಣಾಂಕವು ಅತ್ಯುತ್ತಮ ಅಂದಾಜು ನೀಡುತ್ತದೆ ಆದರೆ ಅದಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರಲು ಕಾರಣವಾಗಬಹುದು, ಇದು ಒಳಹರಿವುಗಳಿಗೆ ಕಾರಣವಾಗಬಹುದು. ಹೀಗೆ ಸಹಿ ಮಾಡದ ಅಂಕಗಣಿತಕ್ಕೆ ಬಳಸಲಾಗುತ್ತದೆ. ಹೀಗಾಗಿ ನಾವು ಮೇಲಿನ ಕಾರ್ಯವನ್ನು ಈ ಕೆಳಗಿನವುಗಳೊಂದಿಗೆ ಅಂದಾಜು ಮಾಡಬಹುದುಃ ಫಂಕ್ ರಿಡ್ಯೂಸ್ (a uint) uint {q: = (a * m)>> k// "> k" ಎಂಬುದು k ಯಿಂದ ಬಿಟ್ಶಿಫ್ಟ್ ಅನ್ನು ಸೂಚಿಸುತ್ತದೆ. a-q * n ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಏಕೆಂದರೆ, ಆ ಕಾರ್ಯದಲ್ಲಿ q ನ ಮೌಲ್ಯವು ತುಂಬಾ ಚಿಕ್ಕದಾಗಿದೆ, ಮತ್ತು ಆದ್ದರಿಂದ a ಸಾಮಾನ್ಯವಾಗಿ ಅಗತ್ಯವಿರುವ ಬದಲು ಒಳಗೆ ಇರುತ್ತದೆ ಎಂದು ಖಾತರಿಪಡಿಸುತ್ತದೆ. ಷರತ್ತುಬದ್ಧ ವ್ಯವಕಲನವು ಇದನ್ನು ಸರಿಪಡಿಸುತ್ತದೆಃ a> = n {a-= n} ರಿಟರ್ನ್ a} ಸಿಂಗಲ್-ವರ್ಡ್ ಬ್ಯಾರೆಟ್ ಗುಣಾಕಾರ ತಿಳಿದಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ಇದು ನಾವು ಸ್ವೀಕರಿಸುವ ಮೊದಲು ಪೂರ್ವಭಾವಿಯಾಗಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಬ್ಯಾರೆಟ್ ಗುಣಾಕಾರವು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ, ಜೊತೆಗಿನ ಹೆಚ್ಚಿನ ಭಾಗವನ್ನು ಅಂದಾಜು ಮಾಡುತ್ತದೆ ಮತ್ತು ಅಂದಾಜನ್ನು ಕಳೆಯುತ್ತದೆ. ಇದು ಗುಣಾಕಾರವಾಗಿರುವುದರಿಂದ, ಪರಿಣಾಮವಾಗಿ ಬರುವ ಮೌಲ್ಯವು ಇದರ ಪ್ರತಿನಿಧಿಯಾಗಿದೆ. ಬ್ಯಾರೆಟ್ ಮತ್ತು ಮಾಂಟ್ಗೊಮೆರಿ ಗುಣಾಕಾರಗಳ ನಡುವಿನ ಪತ್ರವ್ಯವಹಾರವು ಸಹಿ ಮಾಡದ ಮಾಂಟ್ಗೊಮೆರಿ ಗುಣಾಕಾರವು a ನ ಪ್ರತಿನಿಧಿಯನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ ಎಂಬುದನ್ನು ನೆನಪಿಸಿಕೊಳ್ಳಿ. ವಾಸ್ತವವಾಗಿ, ಈ ಮೌಲ್ಯವು ಸಮಾನವಾಗಿರುತ್ತದೆ. ನಾವು ಈ ಕೆಳಗಿನಂತೆ ಹಕ್ಕನ್ನು ಸಾಬೀತುಪಡಿಸುತ್ತೇವೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಪೂರ್ಣಾಂಕ ಅಂದಾಜುಗಳಿಗಾಗಿ, ನಾವು ಹೊಂದಿದ್ದೇವೆ. ಬ್ಯಾರೆಟ್ ಗುಣಾಕಾರದ ವ್ಯಾಪ್ತಿಯನ್ನು ನಾವು ಔಟ್ಪುಟ್ನೊಂದಿಗೆ ಬಂಧಿಸಿದೆವು. ಇದೇ ರೀತಿಯ ಮಿತಿಗಳು ಇತರ ರೀತಿಯ ಪೂರ್ಣಾಂಕ ಅಂದಾಜು ಕಾರ್ಯಗಳನ್ನು ಹೊಂದಿವೆ. ಉದಾಹರಣೆಗೆ, ನಾವು ರೌಂಡಿಂಗ್ ಹಾಫ್ ಅಪ್ ಕಾರ್ಯವನ್ನು ಆಯ್ಕೆ ಮಾಡಿದರೆ, ನಂತರ ನಾವು ಮಲ್ಟಿ-ವರ್ಡ್ ಬ್ಯಾರೆಟ್ ರಿಡಕ್ಷನ್ ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಕಡಿತವನ್ನು ಪರಿಗಣಿಸಲು ಬ್ಯಾರೆಟ್ನ ಪ್ರಾಥಮಿಕ ಪ್ರೇರಣೆ ಆರ್ಎಸ್ಎ ಅನುಷ್ಠಾನವಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರಶ್ನೆಯಲ್ಲಿರುವ ಮೌಲ್ಯಗಳು ಖಂಡಿತವಾಗಿಯೂ ಯಂತ್ರ ಪದದ ಗಾತ್ರವನ್ನು ಮೀರುತ್ತವೆ. ಈ ಪರಿಸ್ಥಿತಿಯಲ್ಲಿ, ಬ್ಯಾರೆಟ್ ಮೇಲಿನ ಏಕ-ಪದದ ಆವೃತ್ತಿಯನ್ನು ಅಂದಾಜು ಮಾಡುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಒದಗಿಸಿದರು ಆದರೆ ಬಹು-ಪದ ಮೌಲ್ಯಗಳಿಗೆ. ವಿವರಗಳಿಗಾಗಿ ಹ್ಯಾಂಡ್ಬುಕ್ ಆಫ್ ಅಪ್ಲೈಡ್ ಕ್ರಿಪ್ಟೋಗ್ರಫಿಯ 14.3.3 ವಿಭಾಗವನ್ನು ನೋಡಿ. ಬಹುಪದಗಳಿಗೆ ಬ್ಯಾರೆಟ್ ಅಲ್ಗಾರಿದಮ್ ಬಹುಪದ ವಿಭಜನೆಗಾಗಿ ಬ್ಯಾರೆಟ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಲು ಸಹ ಸಾಧ್ಯವಿದೆ, ಬಹುಪದಗಳನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುವ ಮೂಲಕ ಮತ್ತು X-adic ಅಂಕಗಣಿತವನ್ನು ಬಳಸುವ ಮೂಲಕ. ಮಾಂಟ್ಗೊಮೆರಿ ಕಡಿತವು ಇದೇ ರೀತಿಯ ಮತ್ತೊಂದು ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಉಲ್ಲೇಖಗಳ ಮೂಲಗಳು ಕಂಪ್ಯೂಟರ್ ಅಂಕಗಣಿತ ಮಾಡ್ಯುಲರ್ ಅಂಕಗಣಿತ