Skip to content

Instantly share code, notes, and snippets.

@fredrik-johansson

fredrik-johansson/gist:2953559

Created June 19, 2012 11:11
Show Gist options
  • Save fredrik-johansson/2953559 to your computer and use it in GitHub Desktop.
Save fredrik-johansson/2953559 to your computer and use it in GitHub Desktop.
Download ZIP
more gcd timings
Raw
gistfile1.txt
n, bits, v1 (using norms), v2, (divisibility only)
balanced input, gcd half the length and bits
2 1 100 ns 100 ns
2 8 97 ns 100 ns
2 64 350 ns 350 ns
2 512 1200 ns 1200 ns
2 4096 17 us 17 us
4 1 7500 ns 6900 ns
4 8 7700 ns 7000 ns
4 64 10000 ns 8599 ns
4 512 89 us 89 us
4 4096 110 us 70 us
8 1 10000 ns 8299 ns
8 8 8200 ns 8700 ns
8 64 18 us 14 us
8 512 170 us 150 us
8 4096 1800 us 1200 us
16 1 15 us 13 us
16 8 12 us 14 us
16 64 29 us 22 us
16 512 180 us 190 us
16 4096 3000 us 2700 us
32 1 30 us 27 us
32 8 27 us 34 us
32 64 140 us 150 us
32 512 530 us 550 us
32 4096 6400 us 5900 us
64 1 100 us 92 us
64 8 120 us 110 us
64 64 470 us 530 us
64 512 1000 us 1200 us
64 4096 14 ms 15 ms
128 1 330 us 320 us
128 8 340 us 340 us
128 64 1800 us 2000 us
128 512 4300 us 5300 us
128 4096 280 ms 53 ms
256 1 1100 us 1100 us
256 8 1200 us 1200 us
256 64 2600 us 5400 us
256 512 14 ms 17 ms
256 4096 170 ms 150 ms
512 1 4000 us 4000 us
512 8 4200 us 4200 us
512 64 9700 us 30 ms
512 512 110 ms 110 ms
512 4096 1850 ms 470 ms
1024 1 12 ms 11 ms
1024 8 12 ms 11 ms
1024 64 26 ms 44 ms
1024 512 130 ms 150 ms
1024 4096 5650 ms 1220 ms
2048 1 30 ms 31 ms
2048 8 31 ms 31 ms
2048 64 71 ms 540 ms
2048 512 340 ms 410 ms
2048 4096 2810 ms 3170 ms
4096 1 81 ms 80 ms
4096 8 82 ms 82 ms
4096 64 190 ms 380 ms
4096 512 900 ms 1080 ms
4096 4096 hangs?
both inputs random (gcd ~= 1)
2 1 7200 ns 6700 ns
2 8 6299 ns 5700 ns
2 64 8100 ns 6299 ns
2 512 31 us 18 us
2 4096 69 us 31 us
4 1 6400 ns 5899 ns
4 8 7100 ns 6400 ns
4 64 10000 ns 7100 ns
4 512 39 us 23 us
4 4096 360 us 170 us
8 1 8500 ns 7600 ns
8 8 9099 ns 7999 ns
8 64 13 us 10000 ns
8 512 42 us 19 us
8 4096 460 us 120 us
16 1 19 us 17 us
16 8 15 us 14 us
16 64 23 us 15 us
16 512 49 us 27 us
16 4096 640 us 250 us
32 1 33 us 30 us
32 8 36 us 33 us
32 64 50 us 38 us
32 512 87 us 49 us
32 4096 790 us 230 us
64 1 100 us 100 us
64 8 110 us 110 us
64 64 120 us 120 us
64 512 160 us 140 us
64 4096 520 us 320 us
128 1 360 us 360 us
128 8 370 us 370 us
128 64 400 us 380 us
128 512 450 us 420 us
128 4096 850 us 640 us
256 1 1300 us 1400 us
256 8 1400 us 1400 us
256 64 1400 us 1400 us
256 512 1500 us 1500 us
256 4096 1700 us 1600 us
512 1 5000 us 4900 us
512 8 4900 us 4900 us
512 64 5000 us 5000 us
512 512 5300 us 5200 us
512 4096 6300 us 6000 us
1024 1 15 ms 15 ms
1024 8 16 ms 15 ms
1024 64 15 ms 15 ms
1024 512 16 ms 16 ms
1024 4096 18 ms 17 ms
2048 1 43 ms 43 ms
2048 8 43 ms 43 ms
2048 64 44 ms 43 ms
2048 512 44 ms 44 ms
2048 4096 47 ms 46 ms
4096 1 110 ms 120 ms
4096 8 120 ms 120 ms
4096 64 120 ms 110 ms
4096 512 120 ms 120 ms
4096 4096 120 ms 130 ms
balanced lengths, imbalanced bits
2 1 98 ns 100 ns
2 8 100 ns 100 ns
2 64 400 ns 400 ns
2 512 1300 ns 1400 ns
2 4096 27 us 27 us
4 1 6800 ns 7000 ns
4 8 6600 ns 7100 ns
4 64 9099 ns 8900 ns
4 512 39 us 22 us
4 4096 280 us 200 us
8 1 9400 ns 8400 ns
8 8 8700 ns 10000 ns
8 64 15 us 12 us
8 512 63 us 31 us
8 4096 470 us 220 us
16 1 11 us 12 us
16 8 19 us 15 us
16 64 33 us 26 us
16 512 73 us 49 us
16 4096 750 us 310 us
32 1 22 us 22 us
32 8 43 us 36 us
32 64 71 us 56 us
32 512 100 us 80 us
32 4096 1400 us 460 us
64 1 100 us 95 us
64 8 130 us 110 us
64 64 250 us 220 us
64 512 480 us 410 us
64 4096 3700 us 2500 us
128 1 310 us 320 us
128 8 360 us 360 us
128 64 690 us 670 us
128 512 1600 us 1600 us
128 4096 13 ms 12 ms
256 1 1100 us 1100 us
256 8 1200 us 1200 us
256 64 2100 us 2000 us
256 512 5000 us 5000 us
256 4096 38 ms 37 ms
512 1 4100 us 4100 us
512 8 4300 us 4300 us
512 64 6400 us 6400 us
512 512 14 ms 15 ms
512 4096 100 ms 100 ms
1024 1 11 ms 12 ms
1024 8 11 ms 12 ms
1024 64 17 ms 17 ms
1024 512 40 ms 40 ms
1024 4096 260 ms 260 ms
2048 1 31 ms 31 ms
2048 8 31 ms 31 ms
2048 64 45 ms 45 ms
2048 512 110 ms 100 ms
2048 4096 1150 ms 1160 ms
4096 1 82 ms 82 ms
4096 8 83 ms 83 ms
4096 64 120 ms 110 ms
4096 512 270 ms 270 ms
4096 4096 1740 ms 1560 ms
balanced lengths, imbalanced bits
2 1 9600 ns 8500 ns
2 8 13 us 11 us
2 64 13 us 14 us
2 512 38 us 31 us
2 4096 470 us 250 us
4 1 12 us 11 us
4 8 14 us 12 us
4 64 17 us 19 us
4 512 48 us 42 us
4 4096 240 us 59 us
8 1 13 us 15 us
8 8 15 us 17 us
8 64 38 us 30 us
8 512 100 us 66 us
8 4096 1400 us 1000 us
16 1 21 us 25 us
16 8 37 us 31 us
16 64 65 us 54 us
16 512 130 us 84 us
16 4096 1000 us 550 us
32 1 48 us 54 us
32 8 71 us 62 us
32 64 93 us 80 us
32 512 150 us 100 us
32 4096 1500 us 440 us
64 1 130 us 150 us
64 8 170 us 170 us
64 64 280 us 260 us
64 512 400 us 380 us
64 4096 1200 us 1000 us
128 1 420 us 450 us
128 8 480 us 480 us
128 64 690 us 680 us
128 512 1300 us 1900 us
128 4096 2000 us 1800 us
256 1 1400 us 1500 us
256 8 1600 us 1600 us
256 64 2000 us 2000 us
256 512 2300 us 2200 us
256 4096 3600 us 3300 us
512 1 5300 us 5200 us
512 8 5300 us 5300 us
512 64 6200 us 6200 us
512 512 13 ms 18 ms
512 4096 28 ms 35 ms
1024 1 16 ms 16 ms
1024 8 15 ms 16 ms
1024 64 17 ms 18 ms
1024 512 19 ms 19 ms
1024 4096 26 ms 27 ms
2048 1 44 ms 44 ms
2048 8 44 ms 44 ms
2048 64 47 ms 46 ms
2048 512 100 ms 49 ms
2048 4096 63 ms 63 ms
4096 1 120 ms 110 ms
4096 8 110 ms 110 ms
4096 64 130 ms 120 ms
4096 512 260 ms 390 ms
4096 4096 180 ms 160 ms
imbalanced length and bits
2 1 7799 ns 7100 ns
2 8 7900 ns 7300 ns
2 64 11 us 9099 ns
2 512 19 us 17 us
2 4096 46 us 34 us
4 1 8100 ns 7300 ns
4 8 10000 ns 8200 ns
4 64 10000 ns 11 us
4 512 15 us 11 us
4 4096 70 us 22 us
8 1 8400 ns 9000 ns
8 8 10000 ns 9300 ns
8 64 11 us 12 us
8 512 31 us 23 us
8 4096 100 us 44 us
16 1 9600 ns 11 us
16 8 12 us 11 us
16 64 14 us 18 us
16 512 27 us 30 us
16 4096 180 us 74 us
32 1 10000 ns 13 us
32 8 11 us 15 us
32 64 34 us 27 us
32 512 62 us 47 us
32 4096 350 us 140 us
64 1 14 us 22 us
64 8 13 us 23 us
64 64 23 us 51 us
64 512 45 us 88 us
64 4096 110 us 200 us
128 1 22 us 35 us
128 8 20 us 38 us
128 64 36 us 84 us
128 512 70 us 160 us
128 4096 270 us 460 us
256 1 35 us 62 us
256 8 71 us 69 us
256 64 75 us 170 us
256 512 130 us 280 us
256 4096 410 us 780 us
512 1 130 us 130 us
512 8 100 us 170 us
512 64 180 us 370 us
512 512 280 us 610 us
512 4096 800 us 1600 us
1024 1 310 us 300 us
1024 8 330 us 310 us
1024 64 370 us 770 us
1024 512 600 us 1300 us
1024 4096 1600 us 3200 us
2048 1 310 us 530 us
2048 8 350 us 610 us
2048 64 710 us 1400 us
2048 512 1100 us 2600 us
2048 4096 6000 us 5600 us
4096 1 1100 us 1000 us
4096 8 1200 us 1200 us
4096 64 2700 us 2400 us
4096 512 5700 us 5400 us
4096 4096 17 ms 16 ms
balanced, gcd large
2 1 7900 ns 7400 ns
2 8 7000 ns 7500 ns
2 64 7999 ns 7400 ns
2 512 7700 ns 7300 ns
2 4096 7600 ns 7100 ns
4 1 7400 ns 8500 ns
4 8 7400 ns 8599 ns
4 64 7400 ns 8400 ns
4 512 7300 ns 8400 ns
4 4096 10000 ns 8800 ns
8 1 11 us 9900 ns
8 8 8500 ns 9500 ns
8 64 11 us 9700 ns
8 512 10000 ns 10000 ns
8 4096 11 us 9500 ns
16 1 15 us 12 us
16 8 14 us 11 us
16 64 15 us 13 us
16 512 15 us 12 us
16 4096 17 us 13 us
32 1 51 us 63 us
32 8 54 us 62 us
32 64 26 us 20 us
32 512 54 us 63 us
32 4096 49 us 62 us
64 1 130 us 180 us
64 8 160 us 180 us
64 64 160 us 180 us
64 512 150 us 160 us
64 4096 130 us 170 us
128 1 390 us 470 us
128 8 410 us 490 us
128 64 420 us 470 us
128 512 410 us 490 us
128 4096 400 us 470 us
256 1 1500 us 1600 us
256 8 1400 us 1600 us
256 64 1600 us 1700 us
256 512 1500 us 1600 us
256 4096 570 us 640 us
512 1 6900 us 7200 us
512 8 6800 us 7200 us
512 64 3900 us 4200 us
512 512 5400 us 5700 us
512 4096 6900 us 7300 us
1024 1 33 ms 33 ms
1024 8 34 ms 35 ms
1024 64 33 ms 34 ms
1024 512 33 ms 34 ms
1024 4096 27 ms 28 ms
2048 1 190 ms 180 ms
2048 8 150 ms 150 ms
2048 64 190 ms 180 ms
2048 512 180 ms 180 ms
2048 4096 180 ms 170 ms
4096 1 1270 ms 1220 ms
4096 8 1210 ms 1190 ms
4096 64 1270 ms 1260 ms
4096 512 1230 ms 1200 ms
4096 4096 1270 ms 1270 ms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment