CODEWITHSUNDEEP
iosunsignedfactorial
Mohamed Emad Hegab
Mohamed Emad Hegab

Reputation: 2675

iOS : unsigned long with big factorial

I'm trying to make factorial method like the following

-(void)getFactorial{
    NSString *numStr = [NSString stringWithFormat:@"%@", _maxTF.text];
    max = strtoull([numStr UTF8String], NULL, 0);
    for (unsigned long i = 1; i< max ; i++) {
        unsigned long factorial = [self factorial:i];
       if(factorial <= max){
          NSLog(@"%lu (%lu!  =  %lu)",i ,i ,factorial);
       }else{
          break;
       }
    }
}

-(unsigned long) factorial:(unsigned long)n
{
    if (n==0) {
        return 1;//TODO make it empty
    }
    else
    {
        return n*[self factorial:n-1];
    }
}

and it's simple and work fine.. till I try number like (18446744073709551615) which by all means should stop when i = 20, but the factorial of 21 is actually smaller than factorial of 20, so it go on till it reach zero.

I can't figure out where is the problem exactly .

Upvotes: 0

Views: 98

Answers (2)

saagarjha
saagarjha

Reputation: 2320

The factorial is larger than the usigned long will allow, causing an overflow (starting at 0 again) making it appear to be smaller.

Upvotes: 2

Ocie Mitchell
Ocie Mitchell

Reputation: 1765

Because you are using an unisgned value, the multiplication results in an overflow. That is why 21! looks smaller than 20! in your application.

log2(21!) = 65.4, so unsigned math is just throwing out the higher order bit.

Upvotes: 2

Related Questions