7 ms·

A nice thing with using a compiled language (like Julia) is that you typically do not need to worry about these type of things. Using the identical code in the

A nice thing with using a compiled language (like Julia) is that you typically do not need to worry about these type of things. Using the identical code in the blog post in Julia (with some trivial syntactic modifications, https://pastebin.com/RGYunpF4 https://pastebin.com/RGYunpF4) we not only get a ~500x speedup but the speed difference is pretty much negligible between all the different implementations: factor_fermat0: 1.599 ms factor_fermat1: 1.488 ms factor_fermat2: 1.387 ms factor_fermat3: 1.421 ms factor_fermat4: 1.422 ms Of course, you should still measure when you optimize, but dealing with issues such as whether a=a+1 or a+=1 is faster seems annoying. At that point, you are benchmarking the language and not your own code.

ColinWright 8y ago
I was surprised to see that your version of 0 ran nearly as fast as the others, despite the multiple calls to the square root. Then I realised that you're using the library sqrt routine, and I wonder if that would be accurate enough for the case I'm usually in where my numbers have hundreds of digits. I don't know what algorithm Julia uses for that, but I've found floats (and their friends) insufficiently accurate. But that's useful feedback - thank you.
- yoklov 8y ago
  I haven't used Julia in quite a while, but given its focus on numerical computation it would be fairly surprising to me if it didn't have the ability to meet your precision needs.
- kristofferc 8y ago
  If you need higher precision you could always either simply bump up the accuracy a bit using e.g. https://github.com/JuliaMath/DoubleDouble.jl https://github.com/JuliaMath/DoubleDouble.jl or you can use the arbitrary precision numbers in Julia (https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/index.html#Arbitrary-Precision-Arithmetic-1 https://docs.julialang.org/en/v1/manual/integers-and-floatin...) The performance will of course change accordingly.
  - ColinWright 8y ago
    Is there an arbitrary precision square root routine? I've not found it ...
    - kristofferc 8y ago
      The concrete routine that is dispatched to is based on the type of the input number. So `sqrt(2.0)` will, in the end, call the assembly-instruction (depending on your specific CPU) `vsqrtss` since the input type is a 64-bit float, `sqrt(Float32(2.0))` will end up calling `vsqrtsd`, `sqrt(big"2.0")` will call the sqrt from the arbitrary precision library (MPFR) since we now have a "BigFloat" number etc. Directly from a Julia REPL session: julia> sqrt(2.0) 1.4142135623730951 julia> sqrt(Float32(2.0)) 1.4142135f0 julia> sqrt(big"2.0") 1.414213562373095048801688724209698078569671875376948073176679737990732478462102 julia> setprecision(512) # Bump the precision 512 julia> sqrt(big"2.0") 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993586
      - ColinWright 8y ago
        Yes, but I'm talking about getting exact BigInt ceil square roots of BigInt inputs. I've not found anything about whether that is supported natively or in a library.
vmchale 8y ago
> the speed difference is pretty much negligible really? I'd say that's quite significant, if it's repeatable.
- ColinWright 8y ago
  The change from 1.6ms to 1.4ms is small compared with the difference I was seeing in the code I was using that calls sqrt. There the change was about 50% to 80%. But in effect it's an algorithm change, so it's not surprising, and it would be interesting to see how it changes as the numbers involved get bigger. That's not why I was doing it in this case, but it is intriguing.
pjmlp 8y ago
Having gone through a Julia training recently, I am betting on it to slowly overtake Python in data analysis, either that, or JIT usage in Python is finally taken seriously.

ColinWright 8y ago

I was surprised to see that your version of 0 ran nearly as fast as the others, despite the multiple calls to the square root. Then I realised that you're using the library sqrt routine, and I wonder if that would be accurate enough for the case I'm usually in where my numbers have hundreds of digits. I don't know what algorithm Julia uses for that, but I've found floats (and their friends) insufficiently accurate. But that's useful feedback - thank you.

yoklov 8y ago
I haven't used Julia in quite a while, but given its focus on numerical computation it would be fairly surprising to me if it didn't have the ability to meet your precision needs.
kristofferc 8y ago
If you need higher precision you could always either simply bump up the accuracy a bit using e.g. https://github.com/JuliaMath/DoubleDouble.jl https://github.com/JuliaMath/DoubleDouble.jl or you can use the arbitrary precision numbers in Julia (https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/index.html#Arbitrary-Precision-Arithmetic-1 https://docs.julialang.org/en/v1/manual/integers-and-floatin...) The performance will of course change accordingly.
- ColinWright 8y ago
  Is there an arbitrary precision square root routine? I've not found it ...
  - kristofferc 8y ago
    The concrete routine that is dispatched to is based on the type of the input number. So `sqrt(2.0)` will, in the end, call the assembly-instruction (depending on your specific CPU) `vsqrtss` since the input type is a 64-bit float, `sqrt(Float32(2.0))` will end up calling `vsqrtsd`, `sqrt(big"2.0")` will call the sqrt from the arbitrary precision library (MPFR) since we now have a "BigFloat" number etc. Directly from a Julia REPL session: julia> sqrt(2.0) 1.4142135623730951 julia> sqrt(Float32(2.0)) 1.4142135f0 julia> sqrt(big"2.0") 1.414213562373095048801688724209698078569671875376948073176679737990732478462102 julia> setprecision(512) # Bump the precision 512 julia> sqrt(big"2.0") 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993586
    - ColinWright 8y ago
      Yes, but I'm talking about getting exact BigInt ceil square roots of BigInt inputs. I've not found anything about whether that is supported natively or in a library.

vmchale 8y ago

> the speed difference is pretty much negligible really? I'd say that's quite significant, if it's repeatable.

ColinWright 8y ago
The change from 1.6ms to 1.4ms is small compared with the difference I was seeing in the code I was using that calls sqrt. There the change was about 50% to 80%. But in effect it's an algorithm change, so it's not surprising, and it would be interesting to see how it changes as the numbers involved get bigger. That's not why I was doing it in this case, but it is intriguing.

pjmlp 8y ago

Having gone through a Julia training recently, I am betting on it to slowly overtake Python in data analysis, either that, or JIT usage in Python is finally taken seriously.