Miller–Rabin primality test#2139
Conversation
| if (n.lt('3317044064679887385961981')) { | ||
| bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41].filter(x => x < n) | ||
| } else { | ||
| const max = Math.min(n.toNumber() - 2, Math.floor(2 * Math.pow(n.decimalPlaces() * Math.log(10), 2))) |
There was a problem hiding this comment.
For this calculation of the max (or min?), you transform Decimal into a regular number. Should these calculations be done as Decimal?
There was a problem hiding this comment.
it should work with conversion to a number even when it will be converted to Infinity as the second part should be small
There was a problem hiding this comment.
Ah yes you're right, then it works just fine indeed 👍
|
Thanks Viktor 👍 , and sorry for the late reply. The code looks good, and it's nice that we can utilize the bignumber library that's already in the library. For reference: #2133 |
|
I have to use some strange thing like |
I'm not sure if |
|
Another thing here: for small integers (< 2**26 or something) the trial division is still faster... especially if to convert from Decimal to a number... can the "BigNumber code" call the "number code" for small integers? |
the digits of the number, but if that number is always less the precision digits, then it will work as well |
yes, an actual number cannot have more digits than the configured maximum (64 by default). Ok then I think all is fine and can be merged, right? |
|
@josdejong , ops... n.decimalPlaces() is the number of decimal places after the decimal comma... this needs to be fixed... |
|
👍 good we're checking this, I'll wait with merging then |
|
@Yaffle I see you made a few commits, is the PR ready to be merged? |
|
@josdejong , yes |
|
Well I've known about it since the '70s (latish) and that predates
Wikipedia so I'd say no. but then again I'm not a lawyer…
…On Mon, Apr 5, 2021 at 8:52 AM Viktor ***@***.***> wrote:
@josdejong <https://github.com/josdejong> , yes
btw, if it is based on pseudo code from Wikipedia, is there some
restrictions?
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<#2139 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAHE7PRYAGWFH4TDENYV2DDTHHFCVANCNFSM4ZRTKXRA>
.
|
I think you can just use the code, but should keep attribution in place (not sure if you must though). See for example https://opensource.stackexchange.com/questions/8262/proper-use-of-wikipedia-code-sample-in-open-source-projects. You already included the link to the source to wikipedia in the PR, so I think all is fine, right? |
@josdejong , the linking is fine |
|
Agree, merging now. Thanks Victor! |
* Miller–Rabin primality test * add tests for some big numbers * Update isPrime.js * Update isPrime.js Co-authored-by: Jos de Jong <wjosdejong@gmail.com>
https://en.wikipedia.org/wiki/Miller–Rabin_primality_test#Deterministic_variants
btw, I don't know how it works...