mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2018-06-19, 17:32   #1
PandaLz
 
Jun 2018

7 Posts
Default Is this viable to fast finding prime numbers?

Been working as hobby on a theorem that can test for primes and generate them using only a fraction of the original number, decided to make a document about it (the best as i could, I'm not mathematician or programmer, so for now is a draft)


If u kindly take a look and give some feedback or contribute on it's development would be awesome :)


http://nbviewer.jupyter.org/github/P...er/index.ipynb


Excuse the abuse on tables but considered that the sets of tables reinforce the explanation and procedure.


If have questions, suggestions or comments please go ahead :)



Thanks in advance :)
PandaLz is offline   Reply With Quote
Old 2018-06-19, 19:38   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133468 Posts
Default

It looks like this method requires storing on the order of sqrt(x) numbers in the sequences[] array, which means that it will be very slow and fill memory for numbers around 22 digits (assuming ~100 gigabits of RAM) and won't work for numbers much larger. You seem to be doing some variant of trial division.

But checking a 100-digit prime should only take a few milliseconds (I don't know what is state-of-the-art).
CRGreathouse is offline   Reply With Quote
Old 2018-06-19, 20:11   #3
PandaLz
 
Jun 2018

7 Posts
Default

Thanks for your feedback :)


Sure is some way of trial division but since is in worst at most 1/3 of the original I thought would be more easy while processing, still have to try for all existing odds between 3 and middle, but observed that if (maybe using some supporting sieve?) to find prime numbers within the range is possible only test for those that are true, still that would add complexity and maybe end up being slower...


And yeah, tested for a set of numbers of 6 digits and tables ended up growing up fast the usage of ram, so maybe looping trough only without actually storing but the values to be tested within the range and if is true or false? also maybe just in case of generating having a set of arrays that hold boolean values where in case to be 0 just mark it as false (could be also by looping i guess) the set of arrays should be ram friendly since will be about middle * (middle / 2) bits.


What u think?
PandaLz is offline   Reply With Quote
Old 2018-06-19, 21:57   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·3·977 Posts
Default

Definitely looping through without storing would be faster. It still won't scale to big numbers but it will be doable for larger numbers.
CRGreathouse is offline   Reply With Quote
Old 2018-06-19, 23:34   #5
PandaLz
 
Jun 2018

1112 Posts
Default

Thanks, will think about what can do to implement that looping and see if can skip some values or think about something else to speed it up :) if have some advice please let me know :)


About programming have 2 questions, I'm hesitant about using gmpy2 for further development, not sure if is compatible with MIT license and can use it for improve the speed, heard it could match c speed when calculating arbitrary precision numbers, you know if is safe to use on my project? And if could be a good idea to further develop in python or pick another language like C/C++ or Rust?


Also one of the things I'm unsure is about the "cost" of processor cycles, for example, mentioned there as one general rule that If start increment the values from right to left from where the rows converge until reach the middle get same result as the trial division made if start from middle and trial division to the right. In resume, on one side have a square root and trial division and from the other have a division and simple addition and subtraction but more quantity of them, which could be more efficient?
PandaLz is offline   Reply With Quote
Old 2018-06-20, 21:16   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111001102 Posts
Default

Quote:
Originally Posted by PandaLz View Post
About programming have 2 questions, I'm hesitant about using gmpy2 for further development, not sure if is compatible with MIT license and can use it for improve the speed, heard it could match c speed when calculating arbitrary precision numbers, you know if is safe to use on my project? And if could be a good idea to further develop in python or pick another language like C/C++ or Rust?
Let me be more general for a moment and say that you can release your code under any license without regard to the license under which the library is released. You wouldn't be able to release the combined source of your code and the library, but for a passion project of this sort I wouldn't really worry about that.

For the project at its current state there's no advantage to moving to a lower-level language like C or Rust. Right now working in a high-level language like Python that lets you make big changes easily is appropriate because you want to be able to change things around a lot rather than worrying about optimizing the code.

Quote:
Originally Posted by PandaLz View Post
Also one of the things I'm unsure is about the "cost" of processor cycles, for example, mentioned there as one general rule that If start increment the values from right to left from where the rows converge until reach the middle get same result as the trial division made if start from middle and trial division to the right. In resume, on one side have a square root and trial division and from the other have a division and simple addition and subtraction but more quantity of them, which could be more efficient?
If you start from the small values ("left to right") you're more likely to find a divisor faster, given random input, so that would be much faster. But if you have a prime you won't find a divisor with any method so the order doesn't matter at all.
CRGreathouse is offline   Reply With Quote
Old 2018-06-20, 23:02   #7
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22×5×11×41 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
You wouldn't be able to release the combined source of your code and the library, but for a passion project of this sort I wouldn't really worry about that.
I find it somewhat interesting that many programmers have a problem interpreting licenses.

Law is simply code, written by humans for humans.

Stallman might not be easy to deal with, but he understands code....
chalsall is offline   Reply With Quote
Old 2018-06-21, 00:07   #8
PandaLz
 
Jun 2018

710 Posts
Default

Oh ok, gonna keep up with python :) sure is more versatile and simple to write and the fact that Jupyter runs the output right there is a big advantage XD

I will not hesitate to use gmpy2 then, no one would complain hopefully, guess if really really need will make a change on the license.

Sure in case of being prime will need to run the whole sequence, still if is faster to discard earlier a non prime could improve the overall run time if is testing a range, maybe will figure out to make it accept parameters to let pick which method would use and measure both times :) still gonna try to find a shorter way somehow


Thanks again for your feedback :)


To see law as code for humans is certainly accurate but unfortunately imho isn't simple enough for most humans find that kind of code clear, wouldn't be law schools otherwise :o
PandaLz is offline   Reply With Quote
Old 2018-06-21, 00:14   #9
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22·5·11·41 Posts
Default

Quote:
Originally Posted by PandaLz View Post
To see law as code for humans is certainly accurate but unfortunately imho isn't simple enough for most humans find that kind of code clear, wouldn't be law schools otherwise
That is why so many are afraid of lawyers.

Seriously...
chalsall is offline   Reply With Quote
Old 2018-06-21, 01:53   #10
PandaLz
 
Jun 2018

716 Posts
Default

Can understand why most people could be afraid, know some very mean lawyers :o but better have one handy if doubtful about legal stuff, one never knows when a question made in time could save from trouble specially before signing things :o
PandaLz is offline   Reply With Quote
Old 2018-06-21, 12:14   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133468 Posts
Default

Quote:
Originally Posted by chalsall View Post
I find it somewhat interesting that many programmers have a problem interpreting licenses.

Law is simply code, written by humans for humans.
Code is written to be read and understood. Contract law is obfuscated. They're worlds apart.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Endorsement Prime Numbers finding algorithm marouane Computer Science & Computational Number Theory 18 2017-11-06 15:41
Pretty Fast Primality Test (for numbers = 3 mod 4) tapion64 Miscellaneous Math 40 2014-04-20 05:43
New method of finding large prime numbers georgelouis@mac Math 41 2011-01-25 21:06
Best settings for finding errors fast Bourni Hardware 8 2006-12-27 13:59
Finding smooth numbers Citrix Math 9 2005-12-31 11:07

All times are UTC. The time now is 22:33.

Sat Jul 4 22:33:54 UTC 2020 up 101 days, 20:06, 1 user, load averages: 1.71, 1.26, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.