Sqrt not giving the correct value

General Usage
1

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

function fermat(n::Int64)
    x = isqrt(n); y = 0.1
    while y%1 != 0
        x+=1
        y = sqrt(x^2 - n)
    end
    println((x-y)  ,", ", (x+y))
end

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.

2

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
6904482456930471488

julia> big(5035000169)^2 - 171190005457
25351226530640023104

julia> typemax(Int)
9223372036854775807
1 Like
3

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)

4

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.

8 Likes
5

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

3 Likes
6

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:

Int1024, UInt1024

You can also use integer types which check for overflow, and/or use those types.

And do:

function fermat(n::Integer)
[..]
y = isqrt(x^2 - n)

julia> fermat(Int128(171190005457))  # correct answers(?)
412909, 414595

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