0

Doing one of my first homeworks of uni, and have ran into this problem:

Task: Find a sum of all n elements where n is the count of numerals in a number (n=1, means 1, 2, 3... 8, 9 for example, answer is 45)

Problem: The code I wrote has gotten all the test answers correctly up to 10 to the power of 9, but when it reaches 10 to the power of 10 territory, then the answers start being wrong, it's really close to what I should be getting, but not quite there (For example, my output = 49499999995499995136, expected result = 49499999995500000000)

Would really appreciate some help/insights, am guessing it's something to do with the variable types, but not quite sure of a possible solution..

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main()
{
    int n;
    double ats = 0, maxi, mini;
    cin >> n;
    maxi = pow(10, n) - 1;
    mini = pow(10, n-1) - 1;
    ats = (maxi * (maxi + 1)) / 2 - (mini * (mini + 1)) / 2;
    cout << setprecision(0) << fixed << ats;
}
Lofu Fox
  • 3
  • 2
  • 3
    `pow` isnt made to be used with `int` arguments.. looking for duplicates – 463035818_is_not_an_ai Sep 25 '20 at 14:09
  • How come it works correctly if int n < 10, but not correctly if int n > 10? And what should I use instead of int then if I may ask? – Lofu Fox Sep 25 '20 at 14:18
  • or this https://stackoverflow.com/a/18581693/4117728 – 463035818_is_not_an_ai Sep 25 '20 at 14:19
  • 1
    @idclev463035818 the issue is actually due to 10^10 * 10^9 exceeding the bits of a `double`. It has little to do with `pow` (I *think*) – rustyx Sep 25 '20 at 14:20
  • Just dumb luck, Lofu. I've seen implementations of `pow` that get smaller numbers like five squared wrong. The computations are done on floating point numbers, and a little bit of fuzz gets into the math turning what should be 25 into 24.9999999. Usually the difference is noticed when 24.99999 is converted into an integer and truncated to 24. – user4581301 Sep 25 '20 at 14:20
  • @rustyx my bad, reopened – 463035818_is_not_an_ai Sep 25 '20 at 14:21
  • somewhat related: https://stackoverflow.com/questions/15851636/why-is-my-integer-math-with-stdpow-giving-the-wrong-answer – 463035818_is_not_an_ai Sep 25 '20 at 14:22
  • Also related: [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) – user4581301 Sep 25 '20 at 14:24
  • 1
    49,499,999,995,500,000,000 is an astronomically big number (10^20). There is no easy way to deal with it without losing precision in standard C++. See [here](https://stackoverflow.com/questions/117429/handling-large-numbers-in-c) for some inspiration. – rustyx Sep 25 '20 at 14:30
  • @rustyx That was my first guess too, that it was surpassing the limits of the variable itself, however, there are some tests in the system made with 10 to the power of 80 or even 10 to the power of 99, all made with c++, so I wonder if there is any other way to go about it or no.. – Lofu Fox Sep 25 '20 at 14:36
  • @user4581301 I have tried reading up on floating points and what not, but I feel too stupid for it yet, the uni course has just started, currently all we have learned was variables, if statements and some loops.. So I really doubt it'd go into more advanced areas yet, maybe the idea of how to solve it I had was wrong in the first place? – Lofu Fox Sep 25 '20 at 14:37
  • If you need 100% precision, you can't use floating point. Integers will give you perfect precision, but they have limited capacity. Usually you can't get past 20 digits, so check with your instructor to see what range is required. If it's too big for conventional integers, you'll have to get or write a big integer library. As for the right way to solve this, [Gauss has some suggestions](http://mathcentral.uregina.ca/qq/database/qq.02.06/jo1.html) – user4581301 Sep 25 '20 at 14:45
  • If you need to support 10^20 and beyond, you definitely need to implement arbitrary precision math. Base-10 addition, multiplication and division by 2 are fairly straightforward to implement by hand e.g. using a `vector` as underlying data type. Just program the same steps you do when doing the math on paper. It's going to take some effort, so better double-check if it's actually needed. – rustyx Sep 25 '20 at 15:09
  • It's usually n limit in programming task's. Do you have any N_max in task description? – Nikxp Sep 25 '20 at 15:10
  • A `double` can only hold about 15 decimal digits of precision. The nearest `double` to 49499999995500000000 is 49499999995500003328. You get a different value to the nearest one due to noise in your calculation. – Bathsheba Sep 25 '20 at 15:11
  • @Nikxp The only max is 10^6 on n (input), but the answers he gets after the input itself are 30 and even 50 digits if Im not mistaken. – Lofu Fox Sep 25 '20 at 15:11
  • @user4581301 Thanks for sharing all those references, I will check them out! – Lofu Fox Sep 25 '20 at 15:12
  • @rustyx Unless my professor is a sadist I really doubt he means for the tasks to take over 30-60 minutes in general, but I think I will end up having to check in with him about this task, maybe it's from a topic we haven't learned yet, cause I have gone a bit forward to get it all done – Lofu Fox Sep 25 '20 at 15:14
  • Personally I think that any implementation of `std::pow` that doesn't return the best `double` for integer arguments is defective. `std::pow` is pretty good in this respect on many platforms. Although of course the standard gives no guarantees of its accuracy. – Bathsheba Sep 25 '20 at 15:14
  • Finally, note that a 32 bit `int` will do horrible things in the 1e9 magnitude. Use a `long long` instead to buy you some more digits. – Bathsheba Sep 25 '20 at 15:16
  • @LofuFox I'm not sure is 10^6 is maxN, or max element (then Nmax = 6) if Nmax = 6, then your own function pow with the long long int type instead of int will help (Use operator for). If n is really 10^6 then you can use rustyx advice with vector or char massive – Nikxp Sep 25 '20 at 15:25
  • [Why does pow(5,2) become 24?](https://stackoverflow.com/q/22264236/995714), [Why does gcc compiler output pow(10,2) as 99 not 100?](https://stackoverflow.com/q/25474351/995714), [Why pow(10,5) = 9,999 in C++](https://stackoverflow.com/q/9704195/995714) – phuclv Sep 25 '20 at 15:31

2 Answers2

0

The main reason of problems is pow() function. It works with double, not int. Loss of accuracy is price for representing huge numbers. There are 3 way's to solve problem:

  1. For small n you can make your own long long int pow(int x, int pow) function. But there is problem, that we can overflow even long long int
  2. Use long arithmetic functions, as @rustyx sayed. You can write your own with vector, or find and include library.
  3. There is Math solution specific for topic's task. It solves the big numbers problem. You can write your formula like ((10^n) - 1) * (10^n) - (10^m - 1) * (10^m)) / 2 , (here m = n-1) Then multiply numbers in numerator. Regroup them. Extract common multiples 10^(n-1). And then you can see, that answer have a structure: X9...9Y0...0 for big enought n, where letter X and Y are constants. So, you can just print the answer "string" without calculating.
Nikxp
  • 355
  • 3
  • 13
  • Thank you for the 3rd point too!, that's actually the way our curators solved that problem as well, now that they shared it with us, just writing the answer down, rather than storing it as a variable :) – Lofu Fox Sep 26 '20 at 20:28
0

I think you're stretching floating points beyond their precision. Let me explain:

The C pow() function takes doubles as arguments. You're passing ints, the compiler is adding the code to convert them to doubles before they reach pow(). (And anyway you're storing it as a double when you get the return value since you declared it that way).

Floating points are called that way precisely because the point "floats". Inside a double there's a sign bit, a few bits for the mantissa and a few bits for the exponent. In binary, elevating to a power of two is equivalent to moving the fractional point to the right (or to the left if you're elevating to a negative number). So basically the exponent is saying where the fractional point is, in binary. The great advantage of using this kind of in-memory representation for doubles is that you get a lot of precision for numbers close to 0, and gradually lose precision as numbers become bigger.

That last thing is exactly what's happening to you. Your number is too large to be stored exactly. So it's being rounded to the closest sum of powers of two (powers of two are the numbers that have all zeroes to the right in binary).

Quick experiment: press F12 in your browser, open the javascript console and type 49499999995499995136. In my case, in chrome, I reproduce the same problem.

If you really really really want precision with such big numbers then you can try some of these libraries, but that's too advanced for a student program, you don't need it. Just add an if block and print an error message if the number that the user typed is too big (professors love that, which is actually quite correct).

annitaq
  • 31
  • 2