0

I noticed that square roots are pretty fast in python.

import time
a = time.time()
print((1234567891011121314151617181920**8)**0.5)
d = time.time()-a
print(d)

output:

2.32305723559e+120
0.0150001049042

That's a 200+ digit number in under 0.1 second!

So what's the algorithm behind all this?

kpie
  • 9,588
  • 5
  • 28
  • 50
  • 1
    Note: The `123...1920**8` is computed as a bigint, and then it is converted to floating-point double for the square root operation. Hence, the square root operates on a 64-bit FP number, not a "200-digit" fully accurate integer. – Nayuki Dec 13 '15 at 05:45

1 Answers1

4

CPython is just calling the C intrinsic pow in this case, letting the compiler do whatever it wants with it. How to: pow(real, real) in x86 is one example of somewhere explaining a fast implementation of pow at a processor level.

Community
  • 1
  • 1
Mike Graham
  • 73,987
  • 14
  • 101
  • 130
  • 2
    @NickBastin, AFAIK it should call libm `sqrt` if you use `math.sqrt`, but in this case where OP did `some_float ** 0.5` we would follow the code path taking us to https://github.com/python/cpython/blob/master/Objects/floatobject.c#L763 – Mike Graham Dec 13 '15 at 05:14
  • Can you clarify exactly how we end up with the `sqrt` call? – Mike Graham Dec 13 '15 at 05:14
  • I did a `dis.dis()` on a func that did a direct sqrt from `** 0.5` on our internal Python, but that appears to be something we optimized. Typical CPython appears to assemble this as `BINARY_POWER`, so I take back my sqrt comment... – Nick Bastin Dec 13 '15 at 05:17