Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:46:09
English
19.Sep 2021

Sieve of Ulam (vertical II)

mathematical description

Instead of sieving all odd numbers by the order of rising numbers,
the numbers are sorted in columns and each colomn is sieved:

1357911131517192123252729
313335373941434547495153555759
616365676971737577798183858789
9193959799101103105107109111113115117119
121123125127129131133135137139141143145147149
151153155157159161163165167169171173175177179
181183185187189191193195197199201203205207209
211213215217219221223225227229231233235237239
241243245247249251253255257259261263265267269
271273275277279281283285287289291293295297299
301303305307309311313315317319321323325327329
331333335337339341343345347349351353355357359
361363365367369371373375377379381383385387389
391393395397399401403405407409411413415417419
421423425427429431433435437439441443445447449
451453455457459461463465467469471473475477479
481483485487489491493495497499501503505507509
511513515517519521523525527529531533535537539
541543545547549551553555557559561563565567569
571573575577579581583585587589591593595597599
601603605607609611613615617619621623625627629
631633635637639641643645647649651653655657659
661663665667669671673675677679681683685687689
691693695697699701703705707709711713715717719
721723725727729731733735737739741743745747749
751753755757759761763765767769771773775777779
781783785787789791793795797799801803805807809
811813815817819821823825827829831833835837839
841843845847849851853855857859861863865867869
871873875877879881883885887889891893895897899

The columns started with 3, 5, 9, 15, 21, 25, 27 can be disregarded because gcd (column, 30)>1

For this example all numbers are smaller than 30*30.
Therefore after sieving the coloumns by the primes < 30 only the primes remains.

Regarding a column where the first number is r.
The first occurance of a prime pi > 5 in this column has to be of the form
pi*t = 1 mod 30
t = pi^(-1) mod 30

The inverse of pi mod 30 can be calculated one time in the beginning of the algorithm.

The first occurance of pi in the row r can be calculated by
y=r*[(pi*pi^(-1)-1) / 30] mod pi

As the value of y.th row is divisible by pi, all values y+pi | pi

All numbers which are divisible by pi are sieved out.

The first column is preset by 0, the numbers are not calculated.
The sieving vertical is made by flipping one bit from 0 to 1 from the starting point up to a.

The primes which remain on the column are representing by the zeros,
All non primes which are representant by 1 are reset to zero for the next column.

The number of zeros are counted.

You get the number of all primes concerning each colonm without the sieved primes.

Results:

Based on a Implementation in Cuda on a graphiccard Geforce 650 with 192 Cuda cores

a) a=2*3*5*7*11*13*17=510.510
numbers below a*a = 260620460100 ~ 2,6 * 10^11
columns which have to be examined 18.1 % = 92.159
Runtime : 17,51 min

b) a=2*3*5*7*11*13*17*19 = 9.699.690
numbers below a*a = 94083986096100 ~ 9,4 * 10^13
columns which have to be examined 17.1 % = 1.658.879
Runtime : ~ 5752 min

For comparison :

a) My best implementation on a single processor needs
228 min for the calculation up to 10^12
(Athlon 64 4000+ 128kbyte 1. Level Cache)
The Cuda implementation is therefore more than three time faster.

Implementation

for Cuda
in Mupad


                                  1, 7, 3

                                 1, 11, 4

                                 1, 13, 3

                                 1, 17, 13

                                 1, 19, 12

                                 1, 23, 13

                                 1, 29, 28

                                 1, FALSE

                                 31, TRUE

                                 61, TRUE

                                 151, TRUE

                                 181, TRUE

                                 211, TRUE

                                 241, TRUE

                                 271, TRUE

                                 331, TRUE

                                 421, TRUE

                                 541, TRUE

                                 571, TRUE

                                 601, TRUE

                                 631, TRUE

                                 661, TRUE

                                 691, TRUE

                                 751, TRUE

                                 811, TRUE

                                  7, 7, 0

                                 7, 11, 6

                                 7, 13, 8

                                 7, 17, 6

                                 7, 19, 8

                                 7, 23, 22

                                 7, 29, 22

                                 37, TRUE

                                 67, TRUE

                                 97, TRUE

                                 127, TRUE

                                 157, TRUE

                                 277, TRUE

                                 307, TRUE

                                 337, TRUE

                                 367, TRUE

                                 397, TRUE

                                 457, TRUE

                                 487, TRUE

                                 547, TRUE

                                 577, TRUE

                                 607, TRUE

                                 727, TRUE

                                 757, TRUE

                                 787, TRUE

                                 877, TRUE

                                 11, 7, 5

                                 11, 11, 0

                                 11, 13, 7

                                 11, 17, 7

                                11, 19, 18

                                 11, 23, 5

                                11, 29, 18

                                 41, TRUE

                                 71, TRUE

                                 101, TRUE

                                 131, TRUE

                                 191, TRUE

                                 251, TRUE

                                 281, TRUE

                                 311, TRUE

                                 401, TRUE

                                 431, TRUE

                                 461, TRUE

                                 491, TRUE

                                 521, TRUE

                                 641, TRUE

                                 701, TRUE

                                 761, TRUE

                                 821, TRUE

                                 881, TRUE

                                 13, 7, 4

                                 13, 11, 8

                                 13, 13, 0

                                13, 17, 16

                                 13, 19, 4

                                 13, 23, 8

                                13, 29, 16

                                 43, TRUE

                                 73, TRUE

                                 103, TRUE

                                 163, TRUE

                                 193, TRUE

                                 223, TRUE

                                 283, TRUE

                                 313, TRUE

                                 373, TRUE

                                 433, TRUE

                                 463, TRUE

                                 523, TRUE

                                 613, TRUE

                                 643, TRUE

                                 673, TRUE

                                 733, TRUE

                                 823, TRUE

                                 853, TRUE

                                 883, TRUE

                                 17, 7, 2

                                 17, 11, 2

                                17, 13, 12

                                 17, 17, 0

                                17, 19, 14

                                17, 23, 14

                                17, 29, 12

                                 47, TRUE

                                 107, TRUE

                                 137, TRUE

                                 167, TRUE

                                 197, TRUE

                                 227, TRUE

                                 257, TRUE

                                 317, TRUE

                                 347, TRUE

                                 467, TRUE

                                 557, TRUE

                                 587, TRUE

                                 617, TRUE

                                 647, TRUE

                                 677, TRUE

                                 797, TRUE

                                 827, TRUE

                                 857, TRUE

                                 887, TRUE

                                 19, 7, 1

                                19, 11, 10

                                 19, 13, 5

                                 19, 17, 9

                                 19, 19, 0

                                19, 23, 17

                                19, 29, 10

                                 79, TRUE

                                 109, TRUE

                                 139, TRUE

                                 199, TRUE

                                 229, TRUE

                                 349, TRUE

                                 379, TRUE

                                 409, TRUE

                                 439, TRUE

                                 499, TRUE

                                 619, TRUE

                                 709, TRUE

                                 739, TRUE

                                 769, TRUE

                                 829, TRUE

                                 859, TRUE

                                 23, 7, 6

                                 23, 11, 4

                                 23, 13, 4

                                23, 17, 10

                                23, 19, 10

                                 23, 23, 0

                                 23, 29, 6

                                 53, TRUE

                                 83, TRUE

                                 113, TRUE

                                 173, TRUE

                                 233, TRUE

                                 263, TRUE

                                 293, TRUE

                                 353, TRUE

                                 383, TRUE

                                 443, TRUE

                                 503, TRUE

                                 563, TRUE

                                 593, TRUE

                                 653, TRUE

                                 683, TRUE

                                 743, TRUE

                                 773, TRUE

                                 863, TRUE

                                 29, 7, 3

                                 29, 11, 6

                                 29, 13, 9

                                 29, 17, 3

                                 29, 19, 6

                                 29, 23, 9

                                 29, 29, 0

                                 59, TRUE

                                 89, TRUE

                                 149, TRUE

                                 179, TRUE

                                 239, TRUE

                                 269, TRUE

                                 359, TRUE

                                 389, TRUE

                                 419, TRUE

                                 449, TRUE

                                 479, TRUE

                                 509, TRUE

                                 569, TRUE

                                 599, TRUE

                                 659, TRUE

                                 719, TRUE

                                 809, TRUE

                                 839, TRUE