Pairwise summation
ಸಂಖ್ಯಾತ್ಮಕ ವಿಶ್ಲೇಷಣೆಯಲ್ಲಿ, ಕ್ಯಾಸ್ಕೇಡ್ ಸಂಕಲನ ಎಂದೂ ಕರೆಯಲಾಗುವ ಜೋಡಿಯಂತೆ ಸಂಕಲನವು ಸೀಮಿತ-ನಿಖರ ಫ್ಲೋಟಿಂಗ್-ಪಾಯಿಂಟ್ ಸಂಖ್ಯೆಗಳ ಅನುಕ್ರಮವನ್ನು ಒಟ್ಟುಗೂಡಿಸುವ ಒಂದು ತಂತ್ರವಾಗಿದ್ದು, ಇದು ಅನುಕ್ರಮದಲ್ಲಿ ಮೊತ್ತವನ್ನು ನಿಷ್ಕಪಟವಾಗಿ ಸಂಗ್ರಹಿಸುವುದಕ್ಕೆ ಹೋಲಿಸಿದರೆ ಸಂಗ್ರಹವಾದ ರೌಂಡ್-ಆಫ್ ದೋಷವನ್ನು ಗಣನೀಯವಾಗಿ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ಕಹಾನ್ ಸಂಕಲನದಂತಹ ಇತರ ತಂತ್ರಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಇನ್ನೂ ಸಣ್ಣ ರೌಂಡ್-ಆಫ್ ದೋಷಗಳನ್ನು ಹೊಂದಿದ್ದರೂ, ಜೋಡಿಯಾಗಿ ಸಂಕಲನವು ಸುಮಾರು ಉತ್ತಮವಾಗಿದೆ (ಲಾಗರಿಥಮಿಕ್ ಅಂಶದಿಂದ ಮಾತ್ರ ಭಿನ್ನವಾಗಿದೆ) ಆದರೆ ಕಡಿಮೆ ಕಂಪ್ಯೂಟೇಶನಲ್ ವೆಚ್ಚವನ್ನು ಹೊಂದಿದೆ-ಇದನ್ನು ಸುಮಾರು ಅದೇ ವೆಚ್ಚವನ್ನು ಹೊಂದಲು ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು (ಮತ್ತು ನಿಖರವಾಗಿ ಅದೇ ಸಂಖ್ಯೆಯ ಅಂಕಗಣಿತದ ಕಾರ್ಯಾಚರಣೆಗಳು) ನಿಷ್ಕಪಟ ಸಂಕಲನ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಅನುಕ್ರಮವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸುವ ಮೂಲಕ, ಪ್ರತಿ ಅರ್ಧವನ್ನು ಒಟ್ಟುಗೂಡಿಸುವ ಮೂಲಕ ಮತ್ತು ಎರಡು ಮೊತ್ತಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ n ಸಂಖ್ಯೆಗಳ xn ಅನುಕ್ರಮದ ಜೋಡಿಯಂತೆ ಸಂಕಲನವು ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ ಒಂದು ವಿಭಜನೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಕ್ರಮಾವಳಿ. ಇದರ ಅತ್ಯಂತ ಕೆಟ್ಟ ರೌಂಡ್ಆಫ್ ದೋಷಗಳು ಹೆಚ್ಚಿನ O (ε ಲಾಗ್ n) ನಲ್ಲಿ ಲಕ್ಷಣರಹಿತವಾಗಿ ಬೆಳೆಯುತ್ತವೆ, ಅಲ್ಲಿ ε ಯಂತ್ರದ ನಿಖರತೆಯಾಗಿದೆ (ಕೆಳಗೆ ಚರ್ಚಿಸಿದಂತೆ ಸ್ಥಿರ ಸ್ಥಿತಿಯ ಸಂಖ್ಯೆಯನ್ನು ಊಹಿಸಿಕೊಳ್ಳಿ). ಹೋಲಿಸಿದರೆ, ಅನುಕ್ರಮದಲ್ಲಿ ಮೊತ್ತವನ್ನು ಸಂಗ್ರಹಿಸುವ ನಿಷ್ಕಪಟ ತಂತ್ರವು (i = 1,., n ಗಾಗಿ ಪ್ರತಿ xi ಒಂದನ್ನು ಒಂದು ಸಮಯದಲ್ಲಿ ಸೇರಿಸುವುದು) ರೌಂಡ್ಆಫ್ ದೋಷಗಳನ್ನು ಹೊಂದಿದ್ದು ಅದು O (εn) ನಂತೆ ಕೆಟ್ಟದಾಗಿ ಬೆಳೆಯುತ್ತದೆ. ಕಹಾನ್ ಸಂಕಲನವು n ನಿಂದ ಸ್ವತಂತ್ರವಾದ ಸರಿಸುಮಾರು O (ε) ನ ಕೆಟ್ಟ-ಕೇಸ್ ದೋಷವನ್ನು ಹೊಂದಿದೆ, ಆದರೆ ಹಲವಾರು ಪಟ್ಟು ಹೆಚ್ಚು ಅಂಕಗಣಿತದ ಕಾರ್ಯಾಚರಣೆಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. ರೌಂಡ್ಆಫ್ ದೋಷಗಳು ಯಾದೃಚ್ಛಿಕವಾಗಿದ್ದರೆ, ಮತ್ತು ನಿರ್ದಿಷ್ಟವಾಗಿ ಯಾದೃಚ್ಛಿಕ ಚಿಹ್ನೆಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಅವು ಯಾದೃಚ್ಛಿಕ ನಡಿಗೆಯನ್ನು ರೂಪಿಸುತ್ತವೆ ಮತ್ತು ದೋಷದ ಬೆಳವಣಿಗೆಯನ್ನು ಜೋಡಿವಾರು ಸಂಕಲನಕ್ಕೆ ಸರಾಸರಿಗೆ ಇಳಿಸಲಾಗುತ್ತದೆ. ಅನೇಕ ವೇಗದ ಫೋರಿಯರ್ ರೂಪಾಂತರ (ಎಫ್ಎಫ್ಟಿ) ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಇದೇ ರೀತಿಯ ಪುನರಾವರ್ತಿತ ಸಂಯೋಜನೆಯು ಕಂಡುಬರುತ್ತದೆ ಮತ್ತು ಇದು ಆ ಎಫ್ಎಫ್ಟಿಗಳ ಅದೇ ನಿಧಾನಗತಿಯ ರೌಂಡ್ಆಫ್ ಶೇಖರಣೆಗೆ ಕಾರಣವಾಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ ಸೂಡೊಕೋಡ್ನಲ್ಲಿ, n ≤ N ಬೇಸ್ ಕೇಸ್ ಆಗಿದ್ದರೆ ಉದ್ದ ≤ 0 ನ ರಚನೆಗೆ ಜೋಡಿಯಾಗಿ ಸಂಕಲನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬರೆಯಬಹುದುಃ s = ಜೋಡಿಯಾಗಿ (x [1. n]): ಸಾಕಷ್ಟು ಸಣ್ಣ ರಚನೆಗೆ ನಿಷ್ಕಪಟ ಸಂಕಲನ s = 0 i = 1 ರಿಂದ n s = s + x [i] ಇಲ್ಲದಿದ್ದರೆ ಭಾಗಿಸಿ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳಿಃ ರಚನೆಯ ಎರಡು ಭಾಗಗಳನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಒಟ್ಟುಗೂಡಿಸಿ m = ಫ್ಲೋರ್ (n/2) s = ಜೋಡಿಯಾಗಿ (x [1. m]) + ಜೋಡಿಯಾಗಿ (x [m [1. n]) ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಸಂಪೂರ್ಣ ಮೊತ್ತವು ಒಂದು ಕೆಟ್ಟ-ಸಂದರ್ಭದ ದೋಷವನ್ನು ಹೊಂದಿದ್ದು, ಅದು ದೊಡ್ಡ n ಗೆ O (ε log n) ಎಂದು ಲಕ್ಷಣರಹಿತವಾಗಿ ಬೆಳೆಯುತ್ತದೆ, ನಿರ್ದಿಷ್ಟ ಷರತ್ತು ಸಂಖ್ಯೆಗೆ (ಕೆಳಗೆ ನೋಡಿ). ಈ ರೀತಿಯ ಕ್ರಮಾವಳಿಯಲ್ಲಿ (ಸಾಮಾನ್ಯವಾಗಿ ವಿಂಗಡಿಸಲು ಮತ್ತು ಕ್ರಮಾವಳಿಗಳನ್ನು ವಶಪಡಿಸಿಕೊಳ್ಳಲು), ಪುನರಾವರ್ತನೆಯ ಓವರ್ಹೆಡ್ ಅನ್ನು ಮರುಪಾವತಿ ಮಾಡಲು ದೊಡ್ಡ ಬೇಸ್ ಕೇಸ್ ಅನ್ನು ಬಳಸುವುದು ಅಪೇಕ್ಷಣೀಯವಾಗಿದೆ. ಎನ್ = 1 ಆಗಿದ್ದರೆ, ಪ್ರತಿ ಇನ್ಪುಟ್ಗೆ ಸರಿಸುಮಾರು ಒಂದು ರಿಕರ್ಸಿವ್ ಸಬ್ರುಟೈನ್ ಕರೆ ಇರುತ್ತದೆ, ಆದರೆ ಪುನರಾವರ್ತನೆಯು ನಿಖರವಾಗಿ ಎನ್ = ಎನ್ ನಲ್ಲಿ ನಿಂತುಹೋದರೆ (ಸರಿಸುಮಾರು) ಪ್ರತಿ ಎನ್/2 ಇನ್ಪುಟ್ಗಳಿಗೆ ಒಂದು ರಿಕರ್ಸಿವ್ ಕರೆ ಇರುತ್ತದೆ. ಎನ್ ಅನ್ನು ಸಾಕಷ್ಟು ದೊಡ್ಡದಾಗಿಸುವ ಮೂಲಕ, ಪುನರಾವರ್ತನೆಯ ಓವರ್ಹೆಡ್ ಅನ್ನು ನಗಣ್ಯಗೊಳಿಸಬಹುದು (ನಿಖರವಾಗಿ ಪುನರಾವರ್ತಿತ ಸಂಕಲನಕ್ಕಾಗಿ ದೊಡ್ಡ ಬೇಸ್ ಕೇಸ್ನ ಈ ತಂತ್ರವನ್ನು ಹೆಚ್ಚಿನ ಕಾರ್ಯಕ್ಷಮತೆಯ ಎಫ್ಎಫ್ಟಿ ಅನುಷ್ಠಾನಗಳಿಂದ ಬಳಸಲಾಗುತ್ತದೆ). N ಅನ್ನು ಲೆಕ್ಕಿಸದೆ, ನಿಖರವಾಗಿ n−1 ಸೇರ್ಪಡೆಗಳನ್ನು ಒಟ್ಟಾರೆಯಾಗಿ ನಡೆಸಲಾಗುತ್ತದೆ, ಇದು ನಿಷ್ಕಪಟ ಸಂಕಲನದಂತೆಯೇ ಇರುತ್ತದೆ, ಆದ್ದರಿಂದ ಮರುಕಳಿಸುವ ಓವರ್ಹೆಡ್ ಅನ್ನು ನಗಣ್ಯಗೊಳಿಸಿದರೆ, ಜೋಡಿಯಂತೆ ಸಂಕಲನವು ಮೂಲಭೂತವಾಗಿ ನಿಷ್ಕಪಟ ಸಂಕಲನಕ್ಕೆ ಸಮಾನವಾದ ಗಣನೆಯ ವೆಚ್ಚವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ಕಲ್ಪನೆಯ ಒಂದು ವ್ಯತ್ಯಾಸವೆಂದರೆ ಪ್ರತಿ ಪುನರಾವರ್ತಿತ ಹಂತದಲ್ಲಿ ಮೊತ್ತವನ್ನು ಬಿ ಬ್ಲಾಕ್ಗಳಾಗಿ ವಿಭಜಿಸುವುದು, ಪ್ರತಿ ಬ್ಲಾಕ್ ಅನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಒಟ್ಟುಗೂಡಿಸುವುದು ಮತ್ತು ನಂತರ ಫಲಿತಾಂಶಗಳನ್ನು ಒಟ್ಟುಗೂಡಿಸುವುದು, ಇದನ್ನು ಅದರ ಪ್ರಸ್ತಾಪಕರು "ಸೂಪರ್ ಬ್ಲಾಕ್" ಅಲ್ಗಾರಿದಮ್ ಎಂದು ಕರೆಯುತ್ತಾರೆ. ಕೊನೆಯ ಹಂತವಾದ b = N ಅನ್ನು ಹೊರತುಪಡಿಸಿ ಮೇಲಿನ ಜೋಡಿಯಾಗಿ ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ಹಂತಕ್ಕೂ b = 2 ಗೆ ಅನುರೂಪವಾಗಿದೆ. ನಿಖರತೆ ಒಂದು n ಮೌಲ್ಯಗಳನ್ನು xi ಅನ್ನು ಒಟ್ಟುಗೂಡಿಸುತ್ತಿದೆ ಎಂದು ಭಾವಿಸೋಣ, i = 1,., n ಗೆ. ನಿಖರವಾದ ಮೊತ್ತವುಃ (ಅನಂತ ನಿಖರತೆಯೊಂದಿಗೆ ಲೆಕ್ಕಹಾಕಲಾಗಿದೆ). ಬೇಸ್ ಕೇಸ್ N = 1 ಗೆ ಜೋಡಿಯಾಗಿ ಸಂಕಲನದೊಂದಿಗೆ, ಅದರ ಬದಲಿಗೆ ಒಂದನ್ನು ಪಡೆಯುತ್ತದೆ, ಅಲ್ಲಿ ದೋಷವು ಮೇಲೆ ಈ ಕೆಳಗಿನವುಗಳಿಂದ ಸೀಮಿತವಾಗಿದೆಃ ಅಲ್ಲಿ ε ಎಂಬುದು ಗಣಿತವನ್ನು ಬಳಸುವ ಯಂತ್ರದ ನಿಖರತೆಯಾಗಿದೆ (ಉದಾ. ಪ್ರಮಾಣಿತ ಡಬಲ್ ನಿಖರ ತೇಲುವ ಬಿಂದುವಿಗೆ ε ≈ 10−16). ಸಾಮಾನ್ಯವಾಗಿ, ಬಡ್ಡಿಯ ಪ್ರಮಾಣವು ಸಾಪೇಕ್ಷ ದೋಷವಾಗಿದೆ, ಆದ್ದರಿಂದ ಇದು ಮೇಲೆ ಈ ಕೆಳಗಿನವುಗಳಿಂದ ಸೀಮಿತವಾಗಿದೆಃ ಸಾಪೇಕ್ಷ ದೋಷಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ಅಭಿವ್ಯಕ್ತಿಯಲ್ಲಿ, ಭಿನ್ನಾಂಶವು ( ನಿಷ್ಪತ್ತಿಯು |xi |/|Σxi |) ಸಂಕಲನ ಸಮಸ್ಯೆಯ ಷರತ್ತು ಸಂಖ್ಯೆಯಾಗಿದೆ. ಮೂಲಭೂತವಾಗಿ, ಷರತ್ತು ಸಂಖ್ಯೆಯು ದೋಷಗಳಿಗೆ ಸಂಕಲನ ಸಮಸ್ಯೆಯ ಆಂತರಿಕ ಸಂವೇದನೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ, ಅದನ್ನು ಹೇಗೆ ಲೆಕ್ಕ ಹಾಕಲಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕಿಸದೆ. ಪ್ರತಿ (ಹಿಂದುಳಿದ ಸ್ಥಿರ) ಸಂಕಲನ ವಿಧಾನದ ಸಾಪೇಕ್ಷ ದೋಷವು ಸ್ಥಿರ ಅಲ್ಗಾರಿದಮ್ನಿಂದ ಸ್ಥಿರ ನಿಖರತೆಯಲ್ಲಿ ಬಂಧಿಸಲ್ಪಟ್ಟಿದೆ (ಅಂದರೆ. ಅನಿಯಂತ್ರಿತ-ನಿಖರ ಅಂಕಗಣಿತವನ್ನು ಬಳಸುವವರಲ್ಲ, ಅಥವಾ ದತ್ತಾಂಶದ ಆಧಾರದ ಮೇಲೆ ಮೆಮೊರಿ ಮತ್ತು ಸಮಯದ ಅವಶ್ಯಕತೆಗಳು ಬದಲಾಗುವ ಕ್ರಮಾವಳಿಗಳೂ ಅಲ್ಲ), ಈ ಷರತ್ತು ಸಂಖ್ಯೆಗೆ ಅನುಪಾತದಲ್ಲಿರುತ್ತವೆ. ಅಸಮರ್ಪಕ ಸ್ಥಿತಿಯ ಸಂಕಲನ ಸಮಸ್ಯೆಯು ಈ ಅನುಪಾತವು ದೊಡ್ಡದಾಗಿದೆ, ಮತ್ತು ಈ ಸಂದರ್ಭದಲ್ಲಿ ಜೋಡಿಯಂತೆ ಸಂಕಲನವೂ ಸಹ ದೊಡ್ಡ ಸಾಪೇಕ್ಷ ದೋಷವನ್ನು ಹೊಂದಿರಬಹುದು. ಉದಾಹರಣೆಗೆ, xi ಎಂಬ ಸಂಕಲನಗಳು ಶೂನ್ಯ ಸರಾಸರಿ ಹೊಂದಿರುವ ಅಸಂಬಂಧಿತ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳಾಗಿದ್ದರೆ, ಮೊತ್ತವು ಯಾದೃಚ್ಛಿಕ ಕ್ರಮವಾಗಿದೆ ಮತ್ತು ಷರತ್ತು ಸಂಖ್ಯೆಯು ಅದಕ್ಕೆ ಅನುಪಾತದಲ್ಲಿ ಬೆಳೆಯುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ಶೂನ್ಯವಲ್ಲದ ಯಾದೃಚ್ಛಿಕ ಇನ್ಪುಟ್ಗಳಿಗೆ ಷರತ್ತು ಸಂಖ್ಯೆ ಸೀಮಿತ ಸ್ಥಿರಾಂಕಕ್ಕೆ ಅಸಿಂಪ್ಟೋಟ್ಗಳು ಎಂದರ್ಥ. ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳು ಋಣಾತ್ಮಕವಲ್ಲದಿದ್ದರೆ, ಷರತ್ತು ಸಂಖ್ಯೆ 1 ಆಗಿರುತ್ತದೆ. ಕ್ರಿಯೆಯಲ್ಲಿ ಛೇದವು ಪರಿಣಾಮಕಾರಿಯಾಗಿ 1 ಆಗಿರುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಏಕೆಂದರೆ n 21/ε ಕ್ರಮಕ್ಕೆ ಬರುವವರೆಗೆ 1ಕ್ಕಿಂತ ತುಂಬಾ ಚಿಕ್ಕದಾಗಿದೆ, ಇದು ಸರಿಸುಮಾರು 101015ರ ದ್ವಿಗುಣ ನಿಖರತೆಯಾಗಿದೆ. ಹೋಲಿಸಿದರೆ, ನಿಷ್ಕಪಟ ಸಂಕಲನಕ್ಕೆ ಬದ್ಧವಾಗಿರುವ ಸಾಪೇಕ್ಷ ದೋಷವು (ಅನುಕ್ರಮದಲ್ಲಿ ಸಂಖ್ಯೆಗಳನ್ನು ಸೇರಿಸುವುದು, ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಪೂರ್ಣಾಂಕ ಮಾಡುವುದು) ಷರತ್ತು ಸಂಖ್ಯೆಯಿಂದ ಗುಣಿಸಿದಾಗ ಬೆಳೆಯುತ್ತದೆ. ಪ್ರಾಯೋಗಿಕವಾಗಿ, ರೌಂಡಿಂಗ್ ದೋಷಗಳು ಶೂನ್ಯ ಸರಾಸರಿಯೊಂದಿಗೆ ಯಾದೃಚ್ಛಿಕ ಚಿಹ್ನೆಯನ್ನು ಹೊಂದಿರುವ ಸಾಧ್ಯತೆಯಿದೆ, ಇದರಿಂದಾಗಿ ಅವು ಯಾದೃಚ್ಛಿಕ ನಡಿಗೆಯನ್ನು ರೂಪಿಸುತ್ತವೆ; ಈ ಸಂದರ್ಭದಲ್ಲಿ, ನಿಷ್ಕಪಟ ಸಂಕಲನವು ಮೂಲ ಸರಾಸರಿ ಚದರ ಸಾಪೇಕ್ಷ ದೋಷವನ್ನು ಹೊಂದಿದ್ದು ಅದು ಬೆಳೆಯುತ್ತದೆ ಮತ್ತು ಜೋಡಿಯಂತೆ ಸಂಕಲನವು ಸರಾಸರಿ ಬೆಳೆಯುವ ದೋಷವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ತಂತ್ರಾಂಶ ಅನುಷ್ಠಾನಗಳು ಜೋಡಿಯಾಗಿ ಸಂಕಲನವು ನ್ಯುಮ್ಪೈ ಮತ್ತು ಜೂಲಿಯಾ ತಾಂತ್ರಿಕ-ಗಣಕಯಂತ್ರ ಭಾಷೆಯಲ್ಲಿ ಪೂರ್ವನಿಯೋಜಿತ ಸಂಕಲನ ಕ್ರಮವಾಗಿದೆ, ಅಲ್ಲಿ ಎರಡೂ ಸಂದರ್ಭಗಳಲ್ಲಿ ಇದು ನಿಷ್ಕಪಟ ಸಂಕಲನಕ್ಕೆ ಹೋಲಿಸಬಹುದಾದ ವೇಗವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಕಂಡುಬಂದಿದೆ (ದೊಡ್ಡ ಬೇಸ್ ಕೇಸ್ನ ಬಳಕೆಗೆ ಧನ್ಯವಾದಗಳು). ಇತರ ತಂತ್ರಾಂಶ ಅನುಷ್ಠಾನಗಳಲ್ಲಿ ಸಿ #ಭಾಷೆಗೆ ಎಚ್. ಪಿ. ಸಿ. ಶಾರ್ಪ್ ಲೈಬ್ರರಿ ಮತ್ತು ಡಿ. ಯಲ್ಲಿ ಸ್ಟ್ಯಾಂಡರ್ಡ್ ಲೈಬ್ರರಿ ಸಂಕಲನ ಸೇರಿವೆ.