[Code] Big Number in Objective-C

August 22, 2015

image

Last staturday morning, my company had an event named Code Challenge season 2015 (because last year we have had this). It’s just like ACM Contest, but the problems are much easier. It aims to us, my colleagues interest with algorithm, and solving complex problems.

Our Code Challenge contains 4 problems, and you must finish 1st one and then you can open 2nd one, and so on; who finish most problems, and less time will become a champion.

  • But first, please give a big claps to Nguyen Hien for organizing and problems’ composing.

And I want to pick one that I found it interesting for me at least, this is a basic problem, it bases on Fibonacci problem, we could easily have a solution for this right away, but, as a final problem, we will expect a tricky here. So too much talking, here is it.

Problem

After a long time in-door researched, Hung found a good approach to attract a girl and he named it “Girl attracting law by Fibonacci approach” that means the number of presents Hung gives to her is increased by Fibonacci sequence. But don’t stop, he extended to version 2 with some customisation by:

T(n+2) = T(n+1) * T(n+1) + T(n)

with T(n) is a number of presents at the nth dating.

Hung of course has a lot of money but wants to trust a girl, so he should give her 0 present at the first and 1 present at the second dating. And following his theory, 5 presents should be given in the 5th dating as explanation below:

1st number = 0

2nd number = 1

3rd number = 12 + 0 = 1

4th number = 12 + 1 = 2

5th number = 22 + 1 = 5

Hung said that he has meet her 13 times and today he wants to know how many present he should give. Could you help Hung?

Tricky

So you guys easily can see here is dealing with number when it is getting big.

Solution

In C# or Java, they already support big number there, in type called BigInterger, which has theoretical limit with 600 millions of decimal digits.

using System;
using System.Numerics;
 
namespace CodeChallengeSolution.Challenge_1
{
    public class GirlAttracion
    {
        public static void Main( string[] args )
        {
            BigInteger a = 0;
            BigInteger b = 1;
 
            for ( int i = 2; i < 14; i++ )
            {
                BigInteger c = BigInteger.Pow( b, 2 ) + a;
                a = b;
                b = c;
            }
 
            Console.WriteLine( b );
        }
    }
}

However, in Objective-C we only have a type that can store maximumly is NSDecimal, but it is useless in this case, when n become 14. There is one way to sovle this, we can use another libs is JKBigInteger. It is a small library to facilitate easy working with big integers in Objective-C. JKBigInteger is a Objective-C wrapper around LibTomMath C library. It is inspired by the Java’s BigInteger. One more thing, it is easy to use and understand.

I just had another approach and implement this into my code:

#import <Foundation/Foundation.h>
#import "JKBigInteger.h"

JKBigInteger *newFibonacciFrom(int number){
    
    if (number == 1) {
        return 0;
    }else if (number == 2){
        return [[JKBigInteger alloc] initWithString:@"1"];
    }else if (number == 3){
        return [[JKBigInteger alloc] initWithString:@"1"];
    }else
    {
        JKBigInteger *a = [newFibonaciFrom(number-1) pow:2];
        JKBigInteger *b = newFibonaciFrom(number-2);
        
        return [a add:b];
    }
}

int main(int argc, const char *argv[]) {
    @autoreleasepool {

        JKBigInteger *result =  newFibonacciFrom(14);
        NSLog(@"result: %@", result);        
    }
    return 0;
}

And we get output, it’s very long result:

64638105755006397399751657042293862808265288222153181563403666991 662296197703537763110206369984643283490348328394553481293046669815 645122599231755513643076418949697829482955771711247616811694484082 216743870448265679506449082061600918173674304530418808523145779706 788967745259684047700164866532967494010162799957198142658558954220 08995518955861274014803958258622817825

If you have any input, pleas feel free to leave comment, I’m very glad when we raise problem and clear them together.

Happy coding.