News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Statistics on primes

Started by daydreamer, February 20, 2025, 11:24:25 PM

Previous topic - Next topic

daydreamer

Hi
I am probably not the only one who like statistics and curves
After looking at list with loads of primes
Would be interesting create statistics for last digits is of number is a prime
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

raymond

Only the terminating digits 1, 3, 7 and 9 can be considered for prime numbers (the only exceptions being the actual prime numbers 2 and 5).

If your sample is large enough, each of those four terminating digits would likely be close to 25%.
Whenever you assume something, you risk being wrong half the time.
https://masm32.com/masmcode/rayfil/index.html

daydreamer

Quote from: raymond on February 21, 2025, 06:27:18 AMOnly the terminating digits 1, 3, 7 and 9 can be considered for prime numbers (the only exceptions being the actual prime numbers 2 and 5).

If your sample is large enough, each of those four terminating digits would likely be close to 25%.
Very big primes BCD it saves lot of CPU cycles with determine ending with even number and '5' using
 test al,1 and cmp al,'5' faster than idiv 5
Or keyboard input string ,process last digit can skip even conversion to integer and rest of prime testing


Take a look at some of two last digits are the same
1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20
1–20   2   3   5   7   11   13   17   19   23   29   31   37   41   43   47   53   59   61   67   71
21–40   73   79   83   89   97   101   103   107   109   113   127   131   137   139   149   151   157   163   167   173
41–60   179   181   191   193   197   199   211   223   227   229   233   239   241   251   257   263   269   271   277   281
61–80   283   293   307   311   313   317   331   337   347   349   353   359   367   373   379   383   389   397   401   409
81–100   419   421   431   433   439   443   449   457   461   463   467   479   487   491   499   503   509   521   523   541
101–120   547   557   563   569   571   577   587   593   599   601   607   613   617   619   631   641   643   647   653   659
121–140   661   673   677   683   691   701   709   719   727   733   739   743   751   757   761   769   773   787   797   809
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

zedd151

#3
Quote from: daydreamer on February 20, 2025, 11:24:25 PMWould be interesting create statistics for last digits is of number is a prime
Quote from: raymond on February 21, 2025, 06:27:18 AMOnly the terminating digits 1, 3, 7 and 9 can be considered for prime numbers (the only exceptions being the actual prime numbers 2 and 5).
If your sample is large enough, each of those four terminating digits would likely be close to 25%.
:thumbsup:

A small test... to count each occurence of the last digit in a set of prime numbers for daydreamer. The code was adapted to tally the last digit in each prime number, and is very untidy - apologies.  :tongue: but it does seem to do what you were looking for. You can add code Magnus, to get the exact floating point percentages.  :biggrin:
Total Primes = 46009215
Primes from 0 until 900000000

0's = 0
1's = 11502079
2's = 1
3's = 11502577
4's = 0
5's = 1
6's = 0
7's = 11502549
8's = 0
9's = 11502008


What I find more interesting about prime numbers daydreamer, are the prime numbers that are exactly 2 apart from another prime number (i.e., 101 and 103). There is a name for those, but it escapes me at the moment...

Later: I looked it up, they are called Twin Primes:smiley:

I noticed a glaring error in the original code. The string buffer was the same size as the array. Now the string buffer is only 16 bytes.

New results:
Total Primes = 88862422
Primes from 0 until 1800000000

0's = 0
1's = 22214927
2's = 1
3's = 22216298
4's = 0
5's = 1
6's = 0
7's = 22216008
8's = 0
9's = 22215187
¯\_(ツ)_/¯   :azn:

'As we don't do "requests", show us your code first.'  -  hutch—

daydreamer

my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

zedd151

Quote from: daydreamer on February 22, 2025, 04:47:42 PMthanks Zedd  :thumbsup:
Not a problem.
The results are pretty much as Raymond suggested above, that they should be. The more prime numbers that are tested, the closer the results will be to 25% of the total of all the prime numbers within a given range.
¯\_(ツ)_/¯   :azn:

'As we don't do "requests", show us your code first.'  -  hutch—

daydreamer

so using a tiny circular buffer containing 1,3,7,9 when prime testing loop from 10 upto desireed range you only need test 40% of numbers
 
my 0-65535 prime LUT ,ca 10% of the numbers in this range are primes
I was thinking output primes write to 1 bit BMP ,but this gif on this page shows it best when you want to image to better understand where primes are
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

zedd151

#7
Quote from: daydreamer on February 22, 2025, 06:32:33 PMso using a tiny circular buffer containing 1,3,7,9 when prime testing loop from 10 upto desireed range you only need test 40% of numbers
 
my 0-65535 prime LUT ,ca 10% of the numbers in this range are primes
I was thinking output primes write to 1 bit BMP ,but this gif on this page shows it best when you want to image to better understand where primes are
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Eulers Sieve, and Wheel Factorization?
The Sieve of Eratosthenes seems much easier to implement (My fully commented version is Here!). Can't wait to see what you come up with Magnus.


Note: I noticed a huge error in the attachment here The buffer for the prime number string was the same size as the array memory (limiting memory to be used for the array)! I have fixed the code and re-attached an improved version in that post. Now you can use more (larger) prime numbers in the test, depending on memory availability of course....
New results:
Total Primes = 88862422
Primes from 0 until 1800000000

0's = 0
1's = 22214927
2's = 1
3's = 22216298
4's = 0
5's = 1
6's = 0
7's = 22216008
8's = 0
9's = 22215187
Seems to be preference for some over the others...
3's the most
7's next most
9's after that
1's the lowest...
Now I question my previous assumption (and raymonds) of whether the number of primes ending with 1,3,7, and 9 will equalize (to very near 25% for each) at some point further along. It wouldn't surprise me if there were already a scholarly paper around about this seemingly apparent discrepancy and an explanation for it.
¯\_(ツ)_/¯   :azn:

'As we don't do "requests", show us your code first.'  -  hutch—

daydreamer

Thanks zedd
Port to 64 bit just for ability to memory allocate up to 64 GB would make a mighty sieve
I only have 20gb,only got started with unfinished code that all of 16 GB

That gif made me remember multiplication table in school ,I realised it was just create such table without *1

So I already made that kinda code in masm,but forgot where I have it,might be possible to find somewhere in forum
Zero 256*256 prime lut array
Mov esi,2
Outer loop: ;esi
Mov ECX,2
Inner loop:; ECX
Mov eax,esi
Mul ECX
Mov [eax+primelut],al
Inc ECX
Cmp ECX,256
Jb inner loop ; jump if below 256
}
Inc esi
Cmp esi,256
Jb outer loop

Input n
If primelut[n] = 0
Print "prime"
Else
Print "not prime"

2:
Make use of fast ssd and disc cache ,include 13k word prime lut 0-65535 range


 
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

zedd151

Magnus, you might find this interesting...
Towards the end of the video they talk about the distributions and percentages of the prime numbers...
https://masm32.com/board/index.php?topic=12553.0
¯\_(ツ)_/¯   :azn:

'As we don't do "requests", show us your code first.'  -  hutch—

jj2007

I gave it a shot using your primes32, zedd. As expected:

1      19618 entries
3      19665 entries
5      1 entries
7      19621 entries
9      19593 entries

With a bigger sample:
1       87063 entries
3       87216 entries
5       1 entries
7       87178 entries
9       87055 entries

One could argue that 3+7 are slightly overrepresented, but it's just 0.16% different.

Relevant code is in lines 10-25 of attached source.

zedd151

Quote from: jj2007 on February 26, 2025, 02:02:32 AMI gave it a shot using your primes32, zedd. As expected:

1      19618 entries
3      19665 entries
5      1 entries
7      19621 entries
9      19593 entries

With a bigger sample:
1       87063 entries
3       87216 entries
5       1 entries
7       87178 entries
9       87055 entries

Relevant code is in lines 10-25 of attached source.
Where is '2'?
Should very well be marked as prime, as the sole even number.  :smiley:
¯\_(ツ)_/¯   :azn:

'As we don't do "requests", show us your code first.'  -  hutch—

zedd151

#12
Apologies, Jochen. I did not initially run the executable in your attachment.
Nice graphical representation of the distribution of prime numbers. I hadn't realised why you attached that, until I did run the exe.  :rolleyes:  My bad.
You should have posted a screenshot so your intention is known.  :greensml:



Quote from: zedd151 on February 26, 2025, 02:13:15 AMWhere is '2'?
Should very well be marked as prime, as the sole even number.  :smiley:
Yes, it doesn't make sense to display 2, or 5 for that matter, since the bar graph for them would not be visible anyway unless the range of primes is very low.
As a bonus, the window is resizable and the bar graph display resizes accordingly. Kudos.  :thumbsup:  :biggrin:
¯\_(ツ)_/¯   :azn:

'As we don't do "requests", show us your code first.'  -  hutch—

daydreamer

jochen great bar graph statistic code  :thumbsup: 
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding