mersenneforum.org Is this viable to fast finding prime numbers?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-06-19, 17:32 #1 PandaLz   Jun 2018 78 Posts 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 :)
 2018-06-19, 19:38 #2 CRGreathouse     Aug 2006 176316 Posts 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).
 2018-06-19, 20:11 #3 PandaLz   Jun 2018 710 Posts 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?
 2018-06-19, 21:57 #4 CRGreathouse     Aug 2006 5,987 Posts Definitely looping through without storing would be faster. It still won't scale to big numbers but it will be doable for larger numbers.
 2018-06-19, 23:34 #5 PandaLz   Jun 2018 7 Posts 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?
2018-06-20, 21:16   #6
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by PandaLz 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 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.

2018-06-20, 23:02   #7
chalsall
If I May

"Chris Halsall"
Sep 2002
Barbados

11,087 Posts

Quote:
 Originally Posted by CRGreathouse 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....

 2018-06-21, 00:07 #8 PandaLz   Jun 2018 7 Posts 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
2018-06-21, 00:14   #9
chalsall
If I May

"Chris Halsall"
Sep 2002
Barbados

11,087 Posts

Quote:
 Originally Posted by PandaLz 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...

 2018-06-21, 01:53 #10 PandaLz   Jun 2018 7 Posts 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
2018-06-21, 12:14   #11
CRGreathouse

Aug 2006

598710 Posts

Quote:
 Originally Posted by chalsall 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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post marouane Computer Science & Computational Number Theory 18 2017-11-06 15:41 tapion64 Miscellaneous Math 40 2014-04-20 05:43 georgelouis@mac Math 41 2011-01-25 21:06 Bourni Hardware 8 2006-12-27 13:59 Citrix Math 9 2005-12-31 11:07

All times are UTC. The time now is 11:56.

Sun Feb 5 11:56:11 UTC 2023 up 171 days, 9:24, 1 user, load averages: 1.55, 1.30, 1.07

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

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