5 ms·

So, Golang and V8 both use this algorithm when you choose to use an arbitrary-precision integer type. In Python (and Ruby?), all integers are arbitrary-precisio

by pansa2 6y ago

So, Golang and V8 both use this algorithm when you choose to use an arbitrary-precision integer type. In Python (and Ruby?), all integers are arbitrary-precision - do those languages also use this algorithm for division?

dragonwriter 6y ago
> In Python (and Ruby?), all integers are arbitrary-precision IIRC, both (well, CPython and MRI) internally use distinct “small integer” and “big integer" representations, but that is transparent to the user. I'd imagine that they different low-level operations are involved depending on the internal type.
- TylerE 6y ago
  "Normal" ints in Python are certainly native. You don't get bignums until you need them. I think, on 32bit platforms (though we're about 10 years removed from actual expirence) they'd go int -> long -> bignum as needed.
  - toolslive 6y ago
    but... are they unboxed?
    - AlexanderDhoore 6y ago
      In python everything is boxed. EDIT See https://news.ycombinator.com/item?id=12418985 https://news.ycombinator.com/item?id=12418985
    - pansa2 6y ago
      Nothing is unboxed in CPython. Other implementations differ - for example, MicroPython supports several encodings for unboxed values. https://github.com/micropython/micropython/blob/4fc2866f45692b05829d71b636724e690b786307/py/mpconfig.h#L68 https://github.com/micropython/micropython/blob/4fc2866f4569...
  - pansa2 6y ago
    > IIRC, both (well, CPython and MRI) internally use distinct “small integer” and “big integer" representations, but that is transparent to the user. This seems to be correct for MRI. Before Ruby 2.4, both `Fixnum` and `Bignum` were exposed to the programmer. In 2016 these were unified into `Integer` from the programmer's point of view, but with "no internal representation change" [0]. > "Normal" ints in Python are certainly native. You don't get bignums until you need them. However, I don't think this is true for current versions of Python. As part of the 2.x => 3.0 transition, Python underwent a similar unification of integer types. Python 2.x exposes both `int` and `long`, and Python 3.x has only `int`. However, internally, 3.x's `int` is represented by `PyLongObject` and the old `PyIntObject` has been removed. Even the small integer cache (which holds the values -5 to 256) was changed from holding `PyIntObject`s in 2.x [1] to hold `PyLongObject`s [2]. So it looks like in Python 3.x, all integers are arbitrary-precision. I believe this was a significant contributor to early versions of Python 3.x being slower than 2.x. [0] https://rubykaigi.org/2016/presentations/tanaka_akr.html https://rubykaigi.org/2016/presentations/tanaka_akr.html [1] https://github.com/python/cpython/blob/8d21aa21f2cbc6d50aab3f420bb23be1d081dac4/Objects/intobject.c#L79 https://github.com/python/cpython/blob/8d21aa21f2cbc6d50aab3... [2] https://github.com/python/cpython/blob/39f643614d03748a5fad462fe7ed26a174a522fa/Include/internal/pycore_interp.h#L306 https://github.com/python/cpython/blob/39f643614d03748a5fad4...
- globular-toast 6y ago
  This is the same as Common Lisp implementations (it might be in the spec, not sure). It's completely transparent, but the nice thing in CL is there is a built-in way to force the compiler to stick to fixnums or bignums so you can avoid branching on overflows etc.
bradfitz 6y ago
Go in practice doesn't actually use the code cited. Most of the math/bits package is recognized by the compiler and intrinsified down into 1 or a few CPU instructions (not function calls) on almost all architectures. In a git checkout of Go, look at e.g. `git grep Div64 src/cmd/compile`.
- smikhanov 6y ago
  Out of interest, when would that code be used? When compiling for an architecture that doesn’t have intrinsics defined?
- pansa2 6y ago
  Thanks, I missed that the Go code in the article was only performing a "128-bit / 64-bit" division. However, based on this comment [0], it looks like Go does use Knuth's algorithm when dividing arbitrary-precision integers. [0] https://github.com/golang/go/blob/2e94401277128f9e08e3319903d1b78c09c4ab98/src/math/big/nat.go#L696 https://github.com/golang/go/blob/2e94401277128f9e08e3319903...

by pansa2 6y ago

dragonwriter 6y ago

> In Python (and Ruby?), all integers are arbitrary-precision IIRC, both (well, CPython and MRI) internally use distinct “small integer” and “big integer" representations, but that is transparent to the user. I'd imagine that they different low-level operations are involved depending on the internal type.

TylerE 6y ago
"Normal" ints in Python are certainly native. You don't get bignums until you need them. I think, on 32bit platforms (though we're about 10 years removed from actual expirence) they'd go int -> long -> bignum as needed.
- toolslive 6y ago
  but... are they unboxed?
  - AlexanderDhoore 6y ago
    In python everything is boxed. EDIT See https://news.ycombinator.com/item?id=12418985 https://news.ycombinator.com/item?id=12418985
  - pansa2 6y ago
    Nothing is unboxed in CPython. Other implementations differ - for example, MicroPython supports several encodings for unboxed values. https://github.com/micropython/micropython/blob/4fc2866f45692b05829d71b636724e690b786307/py/mpconfig.h#L68 https://github.com/micropython/micropython/blob/4fc2866f4569...
- pansa2 6y ago
  > IIRC, both (well, CPython and MRI) internally use distinct “small integer” and “big integer" representations, but that is transparent to the user. This seems to be correct for MRI. Before Ruby 2.4, both `Fixnum` and `Bignum` were exposed to the programmer. In 2016 these were unified into `Integer` from the programmer's point of view, but with "no internal representation change" [0]. > "Normal" ints in Python are certainly native. You don't get bignums until you need them. However, I don't think this is true for current versions of Python. As part of the 2.x => 3.0 transition, Python underwent a similar unification of integer types. Python 2.x exposes both `int` and `long`, and Python 3.x has only `int`. However, internally, 3.x's `int` is represented by `PyLongObject` and the old `PyIntObject` has been removed. Even the small integer cache (which holds the values -5 to 256) was changed from holding `PyIntObject`s in 2.x [1] to hold `PyLongObject`s [2]. So it looks like in Python 3.x, all integers are arbitrary-precision. I believe this was a significant contributor to early versions of Python 3.x being slower than 2.x. [0] https://rubykaigi.org/2016/presentations/tanaka_akr.html https://rubykaigi.org/2016/presentations/tanaka_akr.html [1] https://github.com/python/cpython/blob/8d21aa21f2cbc6d50aab3f420bb23be1d081dac4/Objects/intobject.c#L79 https://github.com/python/cpython/blob/8d21aa21f2cbc6d50aab3... [2] https://github.com/python/cpython/blob/39f643614d03748a5fad462fe7ed26a174a522fa/Include/internal/pycore_interp.h#L306 https://github.com/python/cpython/blob/39f643614d03748a5fad4...
globular-toast 6y ago
This is the same as Common Lisp implementations (it might be in the spec, not sure). It's completely transparent, but the nice thing in CL is there is a built-in way to force the compiler to stick to fixnums or bignums so you can avoid branching on overflows etc.

bradfitz 6y ago

Go in practice doesn't actually use the code cited. Most of the math/bits package is recognized by the compiler and intrinsified down into 1 or a few CPU instructions (not function calls) on almost all architectures. In a git checkout of Go, look at e.g. `git grep Div64 src/cmd/compile`.

smikhanov 6y ago
Out of interest, when would that code be used? When compiling for an architecture that doesn’t have intrinsics defined?
pansa2 6y ago
Thanks, I missed that the Go code in the article was only performing a "128-bit / 64-bit" division. However, based on this comment [0], it looks like Go does use Knuth's algorithm when dividing arbitrary-precision integers. [0] https://github.com/golang/go/blob/2e94401277128f9e08e3319903d1b78c09c4ab98/src/math/big/nat.go#L696 https://github.com/golang/go/blob/2e94401277128f9e08e3319903...