Home primes: Difference between revisions
→{{header|Wren}}: Now uses Pollard Rho to help with factorization. About 150 times quicker than before.
(→{{header|Wren}}: Updated in line with revised task requirements.) |
(→{{header|Wren}}: Now uses Pollard Rho to help with factorization. About 150 times quicker than before.) |
||
Line 208:
{{libheader|Wren-math}}
{{libheader|Wren-big}}
{{libheader|Wren-sort}}
This uses a combination of the Pollard Rho algorithm and wheel based factorization to try and factorize the large numbers involved here in a reasonable time.
<lang ecmascript>import "/math" for Int
import "/big" for BigInt
import "/sort" for Sort
// simple wheel based prime factors routine for BigInt
var
var inc = [4, 2, 4, 2, 4, 6, 2, 6]
var factors = []
while (n%2 == 0) {
factors.add(
n = n / 2
}
while (n%3 == 0) {
factors.add(
n = n / 3
}
while (n%5 == 0) {
factors.add(
n = n / 5
}
Line 242 ⟶ 244:
}
if (n > 1) factors.add(n)
return factors
}
var pollardRho = Fn.new { |n|
var g = Fn.new { |x, y| (x*x + BigInt.one) % n }
var x = BigInt.two
var y = BigInt.two
var z = BigInt.one
var d = BigInt.one
var count = 0
while (true) {
x = g.call(x, n)
y = g.call(g.call(y, n), n)
d = (x - y).abs % n
z = z * d
count = count + 1
if (count == 100) {
d = BigInt.gcd(z, n)
if (d != BigInt.one) break
z = BigInt.one
count = 0
}
}
if (d == n) return BigInt.zero
return d
}
var primeFactors = Fn.new { |n|
var factors = []
while (n > 1) {
if (n > BigInt.maxSmall/100) {
var d = pollardRho.call(n)
if (d != 0) {
factors.addAll(primeFactorsWheel.call(d))
n = n / d
if (n.isProbablePrime(2)) {
factors.add(n)
break
}
} else {
factors.addAll(primeFactorsWheel.call(n))
break
}
} else {
factors.addAll(primeFactorsWheel.call(n))
break
}
}
Sort.insertion(factors)
return factors
}
Line 257 ⟶ 308:
j = BigInt.new(k)
h.add(j)
if (j.isProbablePrime(
for (l in n...0) System.write("HP%(h[n-l])(%(l)) = ")
System.print(h[n])
| |||