Pow precision with unsigned longs

Question

So I am trying to do the pow (x, y). Where x and y are unsigned longs and the result is stored in an unsigned long. This result will be smaller than 2^63 so I should be able to do it. But since it returns a floating point number I get inaccurate results for big numbers. Is there anyway to get an exact result without using external libraries like bignum? I know I could simply do x*x a Y times, but that is what I am trying to avoid because I am trying to make my program faster.

Where is your code? You probably need to round the float to the nearest integer. — owacoder, Oct 22 '15 at 12:49
`pow` does `exp(y*log(x))`, which is fast but it has precision issues. — Déjà vu, Oct 22 '15 at 12:53
This might be of some interest to you: https://en.wikipedia.org/wiki/Exponentiation_by_squaring — user4520, Oct 22 '15 at 12:54
I The problem is that it isn't 1 number inaccurate, but 37. answer = pow( a, b); — LifeisHard, Oct 22 '15 at 12:54
I didn't flag as a duplicate because you didn't know how to do in the first place but you might look at this: http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int — Emilien, Oct 22 '15 at 12:58
by *This result will be smaller than 2^63*, do you mean that the values of `x` and `y` are such that the result will be small enough or do you imply modular arithmetic? If you test for `x` equal to `0` or `1` you should have at most 61 multiplications with a brute force loop, not even worth optimizing. — chqrlie, Oct 22 '15 at 13:39
If you are trying to raise an integer to an integral power to obtain an integral result, then your best option is probably not converting to floating point to obtain an approximate result. I'm sure a very little amount of searching would find you multiple implementations of an integral power function. Even if you can't find it, it's not that hard to write one... — twalberg, Oct 22 '15 at 13:40
why don't you simply compute `unsigned long pow(unsigned long x, unsigned long y);` as `y` multiples of `x` then? — Paul Evans, Oct 23 '15 at 01:35

score 6 · Accepted Answer · edited May 23 '17 at 12:08

6

pow function returns a double which has precision issues and when you will cast it to long then you are most certain to get the precision issue. As far as I know if you dont use a library then it is not possible to get the accurate result using the pow function alone.

You can also look at Exponentiation by squaring and also look at the barak manos answer where you can try to implement your own pow function as

unsigned long long pow(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y > 0)
    {
        if (y & 1)
            res *= x;
        y >>= 1;
        x *= x;
    }
    return res;
}

edited May 23 '17 at 12:08

Community

1
1

answered Oct 22 '15 at 12:55

Rahul Tripathi

168,305
31
280
331

Is that method effective for very big numbers? Like 10000^10000(x^y)? because I want to keep the value under 2^63-1 all the time. So I am trying to get as close as possible to 2^63-1, then I will do my calculation on that part, take the result , and carry it over to the next calculation until my y has become small enough to do my calculation immediately. – LifeisHard Oct 22 '15 at 13:01
2

@LifeisHard: `10000^10000` isn't smaller than `2^63`, so you would have other issues with that. Apart from the fact that you'd need (approximately) 125 other universes to store all those digits in. – Jongware Oct 22 '15 at 13:14
@Jongware: `10000^10000` is larger than 2^63, but will still easily fit on a web page, albeit not in a comment: a `1` followed by 40000 `0`s. – chqrlie Oct 22 '15 at 13:34
@chqrlie: ... `10000^10` is, according to Google's calculator, `1e+40`. That is 10³¹ Gb – a bit large for a web page – and the number under discussion is a full Googol larger. – Jongware Oct 22 '15 at 14:00
@Jongware If the OP were in fact talking about that number as a quantity of bytes to be stored, then, yes that would indeed be rather large for storage on a web page. Looking at it as simply a number however, "10,000,000,000,000,000,000,000,000,000,000,000,000,000", even when written out long-hand with commas, will fit quite comfortably on nearly any web page... – twalberg Oct 22 '15 at 14:52
@Jongware: @twalberg: LifeisHard writes: *10000^10000(x^y)*. I am assuming he means `x=10000` and `y=10000`, but the formula is rather confusing. `10000^10000` in base 10 has exactly 40001 digits. It is much larger than `10000^10`, almost 1000 times more digits, but still fits on a web page. – chqrlie Oct 22 '15 at 15:52
3

Creating a function `unsigned long long pow(unsigned long long x,unsigned int y) ...` is a good way to cause some nasty bugs. C does not have signatures for functions with the same name. That masks/hides the standard-compliant `double pow( double, double ); function. – Andrew Henle Oct 22 '15 at 15:52

Magisch · Answer 2 · 2015-10-22T13:10:16.120

2

pow is by definition inaccurate. It uses exp(y*log(x)) as a way to emulate x ^ y. If you want complete precision you either need to use an external library or make your own version of pow.

edited Oct 22 '15 at 13:10

answered Oct 22 '15 at 12:59

Magisch

7,312
9
36
52

score -1 · Answer 3 · answered Oct 22 '15 at 13:08

-1

I am not sure your code. But i guess your code like this

unsigned long x,y;
x=...//
y=...//

unsigned long res=pow(x,y);

This is not right. Because pow() always return double type.

double pow(double x, double y)

that's why you got double type number.

To get right number you can do like this:

    unsigned long x,y;
    x=...//
    y=...//

    unsigned long res=(unsigned long)pow(x,y);

answered Oct 22 '15 at 13:08

Newaz Hossain

157
1
4

1

This does not solve OP's problem: "since it returns a floating point number I get inaccurate results for big numbers". – Jongware Oct 22 '15 at 13:12
@Jongware are you sure the value of **res** is floating point number. – Newaz Hossain Oct 22 '15 at 13:31
Your explanation is confusing: as long as `pow` is correctly declared via `#include ` the first option poses no problem, the conversion to `unsigned long` is implicit and correct code will be generated by the compiler. Conversely, if `pow` is not declared, adding the explicit conversion does not change anything: the compiler will assume the function to have `int pow(int,int);` prototype and the code generated will be completely wrong. – chqrlie Oct 26 '15 at 07:39

Pow precision with unsigned longs

3 Answers3