1

I'm performing some calculations on arbitrary precision integers using GNU Multiple Precision (GMP) library. Then I need the decimal digits of the result. But not all of them: just, let's say, a hundred of most significant digits (that is, the digits the number starts with) or a selected range of digits from the middle of the number (e.g. digits 100..200 from a 1000-digit number).

Is there any way to do it in GMP?

I couldn't find any functions in the documentation to extract a range of decimal digits as a string. The conversion functions which convert mpz_t to character strings always convert the entire number. One can only specify the radix, but not the starting/ending digit.

Is there any better way to do it other than converting the entire number into a humongous string only to take a small piece of it and throw out the rest?

Edit: What I need is not to control the precision of my numbers or limit it to a particular fixed amount of digits, but selecting a subset of digits from the digit string of the number of arbitrary precision.

Here's an example of what I need:

71316831 = 19821203202357042996...2076482743

The actual number has 1112852 digits, which I contracted into the ....
Now, I need only an arbitrarily chosen substring of this humongous string of digits. For example, the ten most significant digits (1982120320 in this case). Or the digits from 1112841th to 1112849th (21203202 in this case). Or just a single digit at the 1112841th position (2 in this case).

If I were to first convert my GMP number to a string of decimal digits with mpz_get_str, I would have to allocate a tremendous amount of memory for these digits only to use a tiny fraction of them and throw out the rest. (Not to mention that the original mpz_t number in binary representation already eats up quite a lot.)

phuclv
  • 37,963
  • 15
  • 156
  • 475
SasQ
  • 14,009
  • 7
  • 43
  • 43
  • I have the result already calculated and allocated as a binary representation. The only thing I need now is extracting a range of its digits. I'm not going to make any additional calculations on that number, so the concerns about speed are irrelevant here. It can even take several minutes to extract these digits if needed, I don't care, I just need to get them somehow. But since answers seem to start drifting away from the goal, I guess there's no way to do it (because that's when people usually do what they can to avoid the problem at hand and start nitpicking some irrelevant pieces). – SasQ Jan 27 '15 at 11:23
  • Also, allocating 1MB might be bearable, but I didn't say I want to stop at numbers that big. "Arbitrary precision" usually means that they can be much more bigger when needed, and then it *can* start being a problem. – SasQ Jan 27 '15 at 11:24

2 Answers2

1

I don't think you can do that in GMP. However you can use Boost Multiprecision Library

Depending upon the number type, precision may be arbitrarily large (limited only by available memory), fixed at compile time (for example 50 or 100 decimal digits), or a variable controlled at run-time by member functions. The types are expression-template-enabled for better performance than naive user-defined types.

Emphasis mine

Another alternative is ttmath with the type ttmath::Big<e,m> that you can control the needed precision. Any fixed-precision types will work, provided that you only need the most significant digits, as they all drop the low significant digits like how float and double work. Those digits don't affect the high digits of the result, hence can be omitted safely. For instance if you need the high 20 digits then use a type that can store 20 digits and a little more, in order to provide enough data for correct rounding later

For demonstration let's take a simple example of 77 = 823543 and you only need the top 2 digits. Using a 4-digit type for calculation you'll get this

  • 75 = 16807 => round to 1681×10¹ and store
  • 75×7 = 1681×101×7 = 11767*10¹ ≈ 1177×102
  • 75×7×7 = 1177×102×7 = 8232×102

As you can see the top digits are the same even without needing to get the full exact result. Calculating the full precision using GMP not only wastes a lot of time but also memory. Think about the amount of memory you need to store the result of another operation on 2 bigints to get the digits you want. By fixing the precision instead of leaving it at infinite you'll decrease the CPU and memory usage significantly.

If you need the 100th to 200th high order digits then use a type that has enough room for 201 digits and more, and extract those 101 digits after calculation. But this will be more wasteful so you may need to change to an arbitrary-precision (or fixed-precision) type that uses a base that's a power of 10 for its limbs (I'm using GMP notation here). For example if the type uses base 109 then each limb represents 9 digits in the decimal output and you can get arbitrary digit in decimal directly without any conversion from binary to decimal. That means zero waste for the string. I'm not sure which library uses base 10n but you can look at Mini-Pi's implementation which uses base 109, or write it yourself. This way it also work for efficiently getting the high digits

See

phuclv
  • 37,963
  • 15
  • 156
  • 475
  • @Vĩnh PhúcL I'm not talking about limiting the *precision* to a fixed number of digits. I'm talking about reading just a single digit, or a range of digits, from a random place in the digit string. I added an example of what I need in my question. – SasQ Jan 27 '15 at 10:59
  • are you suggesting switching from integer arithmetics to floating point? Note that there are many numbers which cannot be expressed finitely as floating point representation, e.g. 1/10 or 1/3, and when one tries to do it nevertheless, there are rounding errors. (P.S.: I cannot refer your nickname with StackOverflow - it removes it from the comment due to non-standard characters.) – SasQ Jan 27 '15 at 16:02
  • Just press "at sign", L then press tab. If you're using integer arithmetics then there's no 1/10 or 1/3 in your values. So why should you care about that? With large positive exponents then the value is always integer – phuclv Jan 27 '15 at 16:15
  • 1
    actually you should think it as an int with a scale, not a floating-point value – phuclv Jan 28 '15 at 04:25
  • @L: Great analogy! Thanks. And good point about the fractions. As to the "tab" trick... that's the point: it doesn't work. It just moves the focus to the "Add Comment" button. – SasQ Jan 28 '15 at 13:01
  • Then there's some problem with your browser because people always tag me that way, and I also tag them like that. Just press tab and the current match name will automatically be inserted. Things just got a little more complex when some people use pure Chinese characters in their names – phuclv Jan 28 '15 at 16:05
  • @SasQ you don't even need to store a scale if you don't need to know how larger the number is. This way your program will only use pure integer operations. I once used this in a project Euler problem to find the most 10 significant digits. As I don't care how big the number is, I dropped the exponent away and simply use a `long long` then take the high 10 digits of that value after all the calculations. It worked perfectly – phuclv Jan 28 '15 at 16:09
  • Is the source of your program available somewhere? I'd like to take a look at how you did it. – SasQ Jan 28 '15 at 16:23
  • @SasQ I'm afraid that I can't find the source code anymore. But you can solve [problem 13](https://projecteuler.net/problem=13) and then look at the forum discussed that, read robban's approach, it's very similar to mine. There are othe good solutions, too. [Possible spoiler] Notice that all the numbers have the same length, that's why you can do like that even more easily. – phuclv Jan 28 '15 at 16:38
1

If you know the number of decimal digits of x = 7^1316831 in advance, e.g., 1112852. Then you get your lower, say, 10 digits with:

x % (10^10), and the upper 20 digits with:

x / (10^(1112852 - 20)).

Note, I get 19821203202357042995 for the latter; 5 at final, not 6.

Brett Hale
  • 21,653
  • 2
  • 61
  • 90
  • Thanks, although I know the trick with modulus (I use it already for extracting the *least* significant digits), and division, but I hoped I could just use the result already calculated to extract its digits with GMP's functions somehow. But thanks anyway, if the only way to go is some clever arithmetics to shift & mask the decimal digits, then I'll do it that way. Thanks for the idea. And yes, I know the number of digits upfront (e.g. I can calculate the decimal logarithm and take its whole part plus 1). – SasQ Jan 27 '15 at 11:35
  • Thanks for the hint with `NULL`. It will save some unneeded computation perhaps (unless GMP does it anyway internally to get the number of digits). – SasQ Jan 27 '15 at 11:40
  • @SasQ - sorry, I'm was wrong. It *allocates* a block of memory and performs the full conversion if `str == NULL`. You want `mpz_sizeinbase` , which essentially does what you're doing. – Brett Hale Jan 27 '15 at 11:42
  • Now when I think of it, GMP might be the wrong tool for this task. If I need only the most significant digits (for example), perhaps a better idea would be to use some clever calculations to compute only the significant part of the result. In a similar way to when you multiply 987×654=645498 and you want only the most significant digit, 9×6 = **5**4 which nearly gives the most significant digit (**6**), but there's a catch with carries which need to be taken account for. It would be even harder for exponentiation. Huh... I need to think about it some more... – SasQ Jan 27 '15 at 11:49
  • 1
    @SasQ do that with more precision (98*65 = 6370) and round the result properly you'll get the desire value (6) – phuclv Jan 27 '15 at 14:16
  • 1
    Tanks, this really seems to be a better approach to this problem than calculating the entire number just to get some of its digits. Now I just need to think of a way to generalize it to other arithmetical operations (especially exponentiation) without getting into too much computational complexity... – SasQ Jan 27 '15 at 16:09