Hello, I’m new to Julia and I was trying to use for Fermat Factoring problem
I’m having issues with the sqrt not returning the correct value
x = isqrt(n); y = 0.1
while y%1 != 0
y = sqrt(x^2 - n)
println((x-y) ,", ", (x+y))
This code works for small values like 187, and 161423 but when I use n = 171190005457, I was supposed to get 17 and 10070000321. Which I know that there are a few erros, because it doesn’t return me prime numbers at high values.
I tried calculating the sqrt(5035000169^2 - 171190005457) but it doesn’t return me the correct value.
It seems like you are getting integer overflow here, maybe try running it with a type supporting larger values such as Int128 or BigInt?
julia> 5035000169^2 - 171190005457
julia> big(5035000169)^2 - 171190005457
in general be very careful when trying to run number theory stuff in languages with machine number types as default (or put it a different way, you don’t have to be as careful when using Mathematica)
i.e. you generally need to use
BigInt types if you want to do number theory.
A few languages do this for you (Mathematica, Maple, and other computer algebra systems, and Python), but you pay a big performance price for this if you are working with ordinary integers (e.g. loop counters, array indices, etcetera), so performance-oriented languages typically require you to use bignums (arbitrary precision arithmetic) explicitly.
Note that in addition to the integer overflow issue, floating point precision means that you shouldn’t expect
sqrt to do what you want. Instead, you should use
y = isqrt(x^2-n) and check if
y*y == x^2-n
You can use Int128(171190005457), that type is in Base. I’m not sure it’s good advice since it can overflow too, unlike BigInt, though increasingly rare, with larger types. It’s going to be much faster… and e.g.:
You can also use:
You can also use integer types which check for overflow, and/or use those types.
y = isqrt(x^2 - n)
julia> fermat(Int128(171190005457)) # correct answers(?)
Off-topic, googling a bit I found what I didn’t know of (their bold):
Fermat hardware goes beyond Von Neumann architecture to allow Big Data processing without any bottleneck […]
Up to 30x faster
than conventional architectures