Category talk:Wren-math: Difference between revisions
Content added Content deleted
(→Source code: Fixed a bug in Int.primeCount.) |
(→Source code: Int.isPrime now switches automatically from wheel to MR for n >= 2^32.) |
||
Line 335: | Line 335: | ||
static binomial(n, k) { multinomial(n, [k, n-k]) } |
static binomial(n, k) { multinomial(n, [k, n-k]) } |
||
// Private helper method for 'isPrime' method. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
// Returns true if 'n' is prime, false otherwise but uses the |
// Returns true if 'n' is prime, false otherwise but uses the |
||
// Miller-Rabin test which should be faster for 'n' >= 2 ^ 32. |
// Miller-Rabin test which should be faster for 'n' >= 2 ^ 32. |
||
static |
static isPrimeMR_(n) { |
||
if (!n.isInteger || n < 2) return false |
|||
if (n%2 == 0) return n == 2 |
if (n%2 == 0) return n == 2 |
||
if (n%3 == 0) return n == 3 |
if (n%3 == 0) return n == 3 |
||
if (n%5 == 0) return n == 5 |
if (n%5 == 0) return n == 5 |
||
if (n%7 == 0) return n == 7 |
if (n%7 == 0) return n == 7 |
||
⚫ | |||
var a |
var a |
||
if (n < 2047) { |
if (n < 2047) { |
||
Line 423: | Line 392: | ||
} |
} |
||
} |
} |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
// Automatically changes to Miller-Rabin approach if 'n' >= 2 ^ 32. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
return true |
return true |
||
Line 433: | Line 434: | ||
while (true) { |
while (true) { |
||
if (Int.isPrime(n)) return n |
if (Int.isPrime(n)) return n |
||
n = n + 2 |
|||
} |
|||
} |
|||
// As 'nextPrime' method but uses 'isPrime2' rather than 'isPrime'. |
|||
// Should be faster for 'n' >= 2 ^ 32. |
|||
static nextPrime2(n) { |
|||
if (n < 2) return 2 |
|||
n = (n%2 == 0) ? n + 1 : n + 2 |
|||
while (true) { |
|||
if (Int.isPrime2(n)) return n |
|||
n = n + 2 |
n = n + 2 |
||
} |
} |