mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2022-01-05, 13:24   #1
TimoKinnunen
 
"Timo Kinnunen"
Jan 2022
Sweden

1 Posts
Default Need an assessment and help regarding prime numbers.

I made an algorithm (2000 primes per minute) that without dividing (see example below) produces all primes of 2,3,5,7,... I think it is revolutionary.

But I don't know and need your expertise here. If you say that technique already exists, I have already been remedied.

Have you heard of an algorithm that produces prime numbers without the usual test with "a % b == 0"?
Thank you if you answered that question. Of course, I haven't found anything on the net.

Is it possible to become a Doctor in the subject? It's fast because the answer already exists!

// List<PrimeNumberItem> primeNumberItemsList = await App.PrimeNumberRepo.GetAllPrimeNumberItemsAsync();

// //calculate primenumbers the old way
// foreach (PrimeNumberItem primeNumberItem in primeNumberItemsList)
// {
// bool isPrimeNumber = true;
// for (int i = 2; i < int.Parse(primeNumberItem.PrimeNumber); i++)
// {
// if (int.Parse(primeNumberItem.PrimeNumber) % i == 0)
// {
// isPrimeNumber = false;
// break;
// }
// }
// }
TimoKinnunen is offline   Reply With Quote
Old 2022-01-05, 13:30   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×3×17×31 Posts
Default

Quote:
Originally Posted by TimoKinnunen View Post
... without dividing (see example below) ...
// if (int.Parse(primeNumberItem.PrimeNumber) % i == 0)
...
% is just a division in disguise. So your code does use division.

Your code does what is known as trial factoring, TF for short. It isn't revolutionary.

Last fiddled with by retina on 2022-01-05 at 13:32
retina is offline   Reply With Quote
Old 2022-01-05, 14:31   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

27F716 Posts
Default

2000 primes per minute in the lower realms does not sound fast.
Uncwilly is online now   Reply With Quote
Old 2022-01-05, 14:39   #4
axn
 
axn's Avatar
 
Jun 2003

19·277 Posts
Default

Quote:
Originally Posted by TimoKinnunen View Post
I made an algorithm
Well... post your algorithm. Don't post "old way". We know old way. We know more "old ways" than you have heard of. Just post your algorithm and we'll tell you if its already known / good / bad.
axn is offline   Reply With Quote
Old 2022-01-05, 14:45   #5
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

33E16 Posts
Default

Code:
private static int Gcd(int a, int b)
{
    while (a != b)
    {
        if (a > b)
        {
            a -= b;
        }
        else
        {
            b -= a;
        }
    }
    return a;
}

var primes = new List<int>();
primes.Add(2);
for (int i = 3; i < limit; i += 2)
{
    foreach (int prime in primes)
    {
        if (Gcd(prime, i) > 1)
        {
            goto not_prime;
        }
    }
    primes.Add(i);
not_prime: ;
}
This is without division, multiplication and modulo. I bet it is faster than 2000 primes per minute up to a limit.
kruoli is offline   Reply With Quote
Old 2022-01-05, 18:44   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·761 Posts
Default

Welcome to GIMPS (assuming you're here in good faith).
Quote:
Originally Posted by TimoKinnunen View Post
I made an algorithm (2000 primes per minute) that without dividing (see example below) produces all primes of 2,3,5,7,... I think it is revolutionary.
What's revolutionary? Post your source. Document your hardware, software, and operands range for which 2000 primes/minute was achieved.
Show us in detail how what you have done is superior in what respect to any or all of the code examples at
http://rosettacode.org/wiki/Primalit...on%27s_theorem and http://rosettacode.org/wiki/Primality_by_trial_division
If I recall correctly, 2000 very small primes/minute was unremarkable for personal computers of 40 years ago doing simple sieving.

Last fiddled with by kriesel on 2022-01-05 at 18:46
kriesel is online now   Reply With Quote
Old 2022-01-06, 01:23   #7
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·761 Posts
Default

The old way seems deliberately constructed to be inefficient. It's perhaps asking a lot of an optimizing compiler to undo that.
Code:
List<PrimeNumberItem> primeNumberItemsList = await App.PrimeNumberRepo.GetAllPrimeNumberItemsAsync();

//calculate prime numbers the old way
foreach (PrimeNumberItem primeNumberItem in primeNumberItemsList)
{
  bool isPrimeNumber = true;
  for (int i = 2; i < int.Parse(primeNumberItem.PrimeNumber); i++) {
    if (int.Parse(primeNumberItem.PrimeNumber) % i == 0) {
      isPrimeNumber = false;
      break;
    }
  }
}
int.Parse is string to int conversion. Repeatedly on the same operand. Inside a for loop. That's properly done once outside the loop.
i increments by one, testing for factors of 2,3,4,5,6,7, ..., number being tested.
Not odds only with the special case of 2 handled separately, not using previously sieved primes only, not using upper limit of sqrt(number under test), not using wheel, etc etc etc.

Let's see, 2000 primes/minute ~33.3/second from the OP.

I forgot to include Sieve of Eratosthenes earlier.
http://rosettacode.org/wiki/Sieve_of...sthenes#Chapel
The Chapel output corresponds to ~383,080,366.65 primes/minute.
Code:
The first 25 primes are:  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
Count of primes to a million is:  78498.
Found 50847534 primes up to 1,000,000,000 in 7964.05 milliseconds.
The alternate odds-only bit-packed version corresponds to 12,686. primes per MILLISECOND.
Multithreaded Chapel 128.279 msec, ~396. primes/ MICROsecond.

The Fortran result 219 msec for up to a billion on Intel Skylake i5-6500 CPU at 3.2 GHz multithreaded with four cores, corresponds to ~232,180,520 primes/sec.
Plus there's an estimated near-fourfold and a near-double optimization untested.
http://rosettacode.org/wiki/Sieve_of...thenes#Fortran
where it's noted to then get adequate timing, a range to 10 billion is more appropriate than 1 billion. That would put multithreaded Fortran in the gigaprimes/sec range.

Faster way with Haskell: 1.085 seconds, corresponding to 46,864,087./second on Sky Lake i5-2500 CPU @ 3.6 GHz (turbo boost for single threaded)

Single threaded NIM up to a billion in 0.793 sec, with untested further near-four-fold and two-fold optimizations, & multithreading unused.

And all the preceding is without getting into the superior TF parallelism performance available on GPUs.

Last fiddled with by kriesel on 2022-01-06 at 01:36
kriesel is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Congruent prime numbers that preserves the modulo as the largest prime factor of the sum Hugo1177 Miscellaneous Math 5 2021-02-11 07:40
What can you do with 2 prime numbers? VicDiesel Programming 12 2017-04-20 21:16
Prime Numbers Or Not Arxenar Miscellaneous Math 38 2013-06-28 23:26
All odd numbers are prime Citrix Lounge 5 2010-04-05 21:34
Prime numbers Unregistered Miscellaneous Math 8 2008-11-09 07:45

All times are UTC. The time now is 23:07.


Sun Jan 16 23:07:52 UTC 2022 up 177 days, 17:36, 0 users, load averages: 1.05, 1.01, 1.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔