5 ms·

It looks like there is some discussion of the algorithmic options at https://github.com/python/cpython/issues/95778 https://github.com/python/cpython/issues/95

by schoen 4y ago

It looks like there is some discussion of the algorithmic options at https://github.com/python/cpython/issues/95778 https://github.com/python/cpython/issues/95778 https://github.com/python/cpython/issues/90716 https://github.com/python/cpython/issues/90716 Is there something bad going on with Python's internal representation of big integers, too? I thought I might have understood Tim Peters to be saying that in the latter thread. It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot?

klodolph 4y ago
> It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot? It's not the data structures. The data structures are really more or less the same: you have some array of words, with a length and a sign. The only real differences are in the particular length of word that you choose, which is not a very interesting difference. Assembly language optimizations do tend to matter here, because you're working with the carry bit for lots of these operations, and each architecture also has some different way of multiplying numbers. Multiplying numbers is "funny" because it produces two words of output for one word of input. There are also sometimes some different algorithms in use, and GMP uses some different algorithms depending on the size. Here's a page describing the algorithms used by GMP: https://gmplib.org/manual/Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms Here's a description of how carries are propagated: https://gmplib.org/manual/Assembly-Carry-Propagation https://gmplib.org/manual/Assembly-Carry-Propagation IMO, I wouldn't expect my language's built-in bigint type to use the best, most cutting-edge algorithms and lots of hand-tuned assembly. GMP is a specialized library for doing special things.
thehappypm 4y ago
One of the comments showed the incredibly naive approach of just building the integer digit-by-digit: ‘1234’ => 1x1000 + 2x100 + 3x10 + 4x1 Is faster and has room to improve
- tylerhou 4y ago
  This takes (worse than) quadratic time.
  - thehappypm 4y ago
    I’m not sure it does, in the best case. There are d additions, so the addition is linear time. Each multiplication is potentially quadratic, but it seems optimizable since it’s never multiplication of two large numbers—always one large and one small number.
    - singron 4y ago
      Each addition is linear in d, but there are d additions, so it's already quadratic before you even consider the multiplications. In a power-of-2 base, the result of the multiplication is a constant number of digits (because the multiplication is just a shift of a single digit), so the additions could each be constant time in that case.
    - tylerhou 4y ago
      One mistake is assuming that the additions take constant time, but really they take ~n time each because you're adding up n-bit integers. If you accumulate your results from left to right you're adding an n-bit integer with a (~n-3)-bit integer, which results in an n-bit integer, which you add with an (~n-6)-bit integer, and so on. This sums up to \Theta(n^2). Another issue you have not accounted for is how you convert to base two. If you want the final product to be in base two, your additions have to be in base two, so the result of your multiplications have to be in base two, which means you will have to convert 1000, 100, 10, 1 into base two as well. Again this takes \Theta(n^2) time if you cache results (1000_2 = 100_2 *_2 10_2): you're doing n operations, and the cost of each operation is 1, 2, 3, 4, ..., n (times some constant. 10^(n-1) * 10 all in base two takes \Theta(n) time). But it's not actually worse than O(n^2), my mistake.
      - thehappypm 4y ago
        They’re probably seeing real-world performance being pretty good with this approach for some other reason then, perhaps it’s quadratic but those additions and multiplications are fast in practice so the O(n^2) badness doesn’t come up for a while

by schoen 4y ago

klodolph 4y ago

> It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot? It's not the data structures. The data structures are really more or less the same: you have some array of words, with a length and a sign. The only real differences are in the particular length of word that you choose, which is not a very interesting difference. Assembly language optimizations do tend to matter here, because you're working with the carry bit for lots of these operations, and each architecture also has some different way of multiplying numbers. Multiplying numbers is "funny" because it produces two words of output for one word of input. There are also sometimes some different algorithms in use, and GMP uses some different algorithms depending on the size. Here's a page describing the algorithms used by GMP: https://gmplib.org/manual/Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms Here's a description of how carries are propagated: https://gmplib.org/manual/Assembly-Carry-Propagation https://gmplib.org/manual/Assembly-Carry-Propagation IMO, I wouldn't expect my language's built-in bigint type to use the best, most cutting-edge algorithms and lots of hand-tuned assembly. GMP is a specialized library for doing special things.

thehappypm 4y ago

One of the comments showed the incredibly naive approach of just building the integer digit-by-digit: ‘1234’ => 1x1000 + 2x100 + 3x10 + 4x1 Is faster and has room to improve

tylerhou 4y ago
This takes (worse than) quadratic time.
- thehappypm 4y ago
  I’m not sure it does, in the best case. There are d additions, so the addition is linear time. Each multiplication is potentially quadratic, but it seems optimizable since it’s never multiplication of two large numbers—always one large and one small number.
  - singron 4y ago
    Each addition is linear in d, but there are d additions, so it's already quadratic before you even consider the multiplications. In a power-of-2 base, the result of the multiplication is a constant number of digits (because the multiplication is just a shift of a single digit), so the additions could each be constant time in that case.
  - tylerhou 4y ago
    One mistake is assuming that the additions take constant time, but really they take ~n time each because you're adding up n-bit integers. If you accumulate your results from left to right you're adding an n-bit integer with a (~n-3)-bit integer, which results in an n-bit integer, which you add with an (~n-6)-bit integer, and so on. This sums up to \Theta(n^2). Another issue you have not accounted for is how you convert to base two. If you want the final product to be in base two, your additions have to be in base two, so the result of your multiplications have to be in base two, which means you will have to convert 1000, 100, 10, 1 into base two as well. Again this takes \Theta(n^2) time if you cache results (1000_2 = 100_2 *_2 10_2): you're doing n operations, and the cost of each operation is 1, 2, 3, 4, ..., n (times some constant. 10^(n-1) * 10 all in base two takes \Theta(n) time). But it's not actually worse than O(n^2), my mistake.
    - thehappypm 4y ago
      They’re probably seeing real-world performance being pretty good with this approach for some other reason then, perhaps it’s quadratic but those additions and multiplications are fast in practice so the O(n^2) badness doesn’t come up for a while