0

I'm trying to multiply 2, 3 digit numbers. I used 2 for loops (nested) and multiplied each digit of num1 with num2, and shifted each result to the appropriate place using pow(). So the problem is pow(10,3) is coming out to be 299 instead of 300.

I haven't tried much as but used printf to find what is actually happening in the runtime and this is what I have found. the values of tempR after shift should be
5,40,300,100,800,6000,1500,12000,90000
but are coming as
5,40,299,100,799,6000,1500,12000,89999

int main(void)
{
    int result; // final result 
    int  tempR; // temporary for each iteration
    char a[] = "345"; // number 1
    char b[] = "321"; // number 2
    for(int i = 2;i>= 0 ; i --)
    {
        for(int j = 2;j >= 0 ; j --)
        {
            int shift = abs(i-2 + j -2);
            printf("%d\n",shift);  //used to see the values of shift. 
                                      //and it is coming as expected
            tempR = (int)(b[i] - '0') * (int)(a[j] - '0');
            printf("%d \n",tempR);    // value to tempR is perfect
            tempR = tempR*pow(10,shift);        
            printf("%d \n",tempR);  // here the problem starts
            result += tempR;
        }
    }

    printf("%d",result);
}
WedaPashi
  • 3,561
  • 26
  • 42
Bhagya Singh
  • 29
  • 4

4 Answers4

2

Although IEEE754 (ubiquitous on desktop systems) is required to return the best possible floating point value for certain operators such as addition, multiplication, division, and subtraction, and certain functions such as sqrt, this does not apply to pow.

pow(x, y) can and often is implemented as exp(y * ln (x)). Hopefully you can see that this can cause result to "go off" spectacularly when pow is used with seemingly trivial integral arguments and the result truncated to int.

There are C implementations out there that have more accurate implementations of pow than the one you have, particularly for integral arguments. If such accuracy is required, then you could move your toolset to such an implementation. Borrowing an implementation of pow from a respected mathematics library is also an option, else roll your own. Using round is also a technique, if a little kludgy if you get my meaning.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
  • On the right track, but I am unaware that `pow` is “often” implemented as `exp(y * ln(x))` or that common `pow` implementations are wrong “spectacularly”. `pow` may be implemented in part by multiplying some aspect of `y` by an approximated logarithm of some aspect of `x`, but the full implementation usually involves more than that (notably, it is unlikely `x` would be treated merely as a value rather than having its floating-point representation dissected for separate treatment). – Eric Postpischil Jun 10 '19 at 11:10
  • As for the suggestion to “borrow” an implementation of `pow` that “takes integral arguments”, that would not be an implementation of `pow` but would be an implementation of exponentiation, and it is overkill for OP’s case, which just needs track a power of ten by multiplying by ten at appropriate times. – Eric Postpischil Jun 10 '19 at 11:11
  • @EricPostpischil: Yes my answer was poorly drafted. It's the truncation to `int` that causes the issue. – Bathsheba Jun 10 '19 at 11:12
  • It is actually the bad implementation of `pow` that causes the issue. `pow` can be and has been implemented in ways that would work here. The `pow` the OP is using returns incorrect results, so it is defective. – Eric Postpischil Jun 10 '19 at 11:12
  • @EricPostpischil: I'm not so sure about that. It's the application of a piecewise discontinuous function (conversion to `int`) applied to a function evaluated in floating point that's the issue. Using the C `pow` function with integral arguments and expecting the correct integral type result is a misuse of the function. – Bathsheba Jun 10 '19 at 11:14
  • It is not a misuse of the function. Early implementations had the excuse that the knowledge of implementing these functions had not been well developed, but that is no longer true. `pow` is implementable with sub-ULP accuracy and good performance, and sub-ULP accuracy guarantees exact results when exact results are representable. Conversion to `int` is piecewise continuous, not piecewise discontinuous (I do not think that means anything), but that is not an impediment in this case. – Eric Postpischil Jun 10 '19 at 13:58
  • Another way of looking at is this: What could be fixed to make this work? The conversion to `int` is working; it converts 99.99…5 to 99 and 100 to 100. The `double` format is working; it represents 100 as 100 and 99.999…5 as 99.999…5. The part that is not working is the `pow` implementation; for `pow(10, 2)`, it returns 99.999…5 when the actual result is 100. Fixing the `pow` implementation fixes this problem. That’s the broken part which can be fixed to make this work. The floating-point format is not broken, and there is no “fix” for that that would make this code work. – Eric Postpischil Jun 10 '19 at 14:00
  • @EricPostpischil; Yet another edit although I think we will have to agree to disagree on the misuse part: `pow` has its very many usages where it not returning the best available value is not an issue, but using it with a truncation to int is the problem. But I'm repeating myself. To my mind it's not too much different to using, for example, sin and cos with a large argument where you ought to consider and adapt the argument to the familiar periodicity. – Bathsheba Jun 10 '19 at 14:13
  • @EricPostpischil Correctly converting the `double` to an `int` by rounding rather than truncation would fix the code and make it work. The problem calls for getting the nearest integer and the code foolishly truncates. – David Schwartz Jun 10 '19 at 18:47
  • @DavidSchwartz: Changing the rounding would be a kludge: The operation is performing its intended function, so changing it is a workaround, not a fix. `pow` is deviating from its intended function; changing it to return the correct result is a fix, not a workaround. – Eric Postpischil Jun 10 '19 at 18:55
  • @EricPostpischil Relying on the range of integer values needed being exactly represented is a kludge and, in fact, it's exactly what caused this problem. – David Schwartz Jun 10 '19 at 23:58
  • @DavidSchwartz: Why is it a kludge? What software makes it not work? The conversion to `int` satisfies its specification completely. The `double` format satisfies its specification completely. The `pow` implementation does not satisfy its specification completely. That is all the relevant software for this. The remedy you propose is not to use this method. Why is that a good remedy? Something does not work, so we should not use it? A better remedy is to fix the deficient software. That software is clearly `pow`. – Eric Postpischil Jun 11 '19 at 00:19
  • @DavidSchwartz: There is no question that `pow` is deficient. It is just that you and others accept the state of the world as is instead of asking for a fix. It ought to be widely regarded that a `pow` that returns incorrect results when exact results are representable is subpar and should not be accepted by customers. Nobody would accept a `strcmp` function that returned incorrect results when correct results were feasible. Nobody would accept a `qsort` that returned unsorted data when sorted data was possible. Why should `pow` be any different? Why are you granting slack when none is needed? – Eric Postpischil Jun 11 '19 at 00:25
  • @EricPostpischil Because it's well-known and well-understood that floating point math will not produce exact results when chopped to integers, even in cases where it could do so. I agree that a better implementation of `pow` would make this broken code happen to work rather than happening to not work, but that does't change the fact that the problem is this code is bad. – David Schwartz Jun 13 '19 at 04:40
  • @DavidSchwartz: “Because it is well-known and well-understood” is an argument that people should not use floating-point because people know you should not use floating-point. It is nonsense and is not based on the specifications or properties of floating-point formats and operations. – Eric Postpischil Jun 13 '19 at 11:48
  • @EricPostpischil I wouldn't quite go that far. I'd just say you shouldn't use the operations that are known to cause problems, such as chopping to an integer and expecting an exact result. – David Schwartz Jun 13 '19 at 19:20
1

Never use float functions for the integer calculations. Your pow result almost never will be precise. In this case it is slightly below 300 and the cast to integer makes it 299.

0___________
  • 60,014
  • 4
  • 34
  • 74
0

The pow function operates on doubles. Doubles use finite precision. Conversion back to integer chops rather than rounding.

Finite precision is like representing 1/3 as 0.333333. If you do 9 * 1/3 and chop to an integer, you'll get 2 instead of 3 because 9 * 1/3 will give 2.999997 which chops to two.

This same kind of rounding and chopping is causing you to be off by one. You could also round by adding 0.5 before chopping to an integer, but I wouldn't suggest it.

Don't pass integers through doubles and back if you expect exact answers.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • This is not a `double` or floating-point problem. Correct results for the cases in the question are representable in `double`, and implementing a `pow` that returns exact results for all cases where exact results are representable is a solved problem. So the cause of the problem is a bad `pow` implementation, not a floating-point limitation. – Eric Postpischil Jun 10 '19 at 11:04
  • I don't agree. You list a bunch of things that just happen to be true. But that's not the core problem with this code. The core problem with this code is that it truncates a `double` to an `int` expecting to get exactly the right integer result. That is a known-broken pattern that makes this code absurdly fragile. – David Schwartz Jun 10 '19 at 18:48
  • No, these things do not “just happen to be true.” They are not matters of chance or mere happenstance. They are intentional. The conversion to integer satisfies its goal; it produces correct results for its purpose. The `double` format satisfies its goal; it is capable of representing values as intended. The `pow` implementation does not satisfy its goal; it returns a mathematically incorrect result when the correct result is desired and achievable. Conversion to `int` works, `double` works, `pow` is broken. – Eric Postpischil Jun 10 '19 at 18:59
-1

Others have mentioned that pow does not yield exact results, and if you convert the result to an integer there's a high risk of loss of precision. Especially since if you assign a float type to an integer type, the result get truncated rather than rounded. Read more here: Is floating math broken?

The most convenient solution is to write your own integer variant of pow. It can look like this:

int int_pow(int num, int e) 
{
    int ret = 1;
    while(e-- > 0) 
        ret *= num;

    return ret;
}

Note that it will not work if e is negative or if both num and e is 0. It also have no protection for overflow. It just shows the idea.

In your particular case, you could write a very specialized variant based on 10:

unsigned int pow10(unsigned int e) 
{
    unsigned int ret = 1;
    while(e-- > 0) 
        ret *= 10;

    return ret;
}
klutt
  • 30,332
  • 17
  • 55
  • 95