Unexpected behaviour when inserting object into NSMutableArray

Question

So I've been working on Project Euler problem 25 in Objective-C and I ran up against the size limit of NSDecimalNumber. So after attempting to use other code libraries I decided to re-represent my Fibonacci number, first as arrays of ints then NSArrays of NSNumbers. Each cell in the array would be one digit. Then I could add to large numbers together digit by digit up to the 1000th digit. Unfortunately something goes wrong, my carry is correct but the digit before the last carry seems to always be zero.

I've tried calculating the 8th Fibonacci number and the 12th Fibonacci number and get the same behaviour. Instead of getting 13 and 144 I get 10 and 104. I sum the digits correctly but

[nextFib insertObject: [NSNumber numberWithInt:digitSum] atIndex: arrayIndex];

Doesn't seem to be doing what I expect. digitSum is a 3 and a 4 in both instances, but once my method returns the next fibonacci number as an NSArray I have a 0 where I expected a 3 or a 4. I've tried stepping through it, and I'm baffled. It seems to work some of the time but other times the NSNumber I create on the fly is not having the value I expect. Here is my entire method:

+ (NSArray*) nextBigFibonancci: (NSArray*) fibZero After: (NSArray*) fibOne
{
  // It's come to manually adding digits in one thousand count arrays.
  // I can't return or pass arrays... will have to use NSArrays for everything, version at least 4.0
  // Since XCode 4.5 I can use array[i] and other array literals... Lets just get it working...

  // Works for Fib 1 and Fib 2 and Fib 3, but not Fib 12...

  int fibZeroDigits = [fibZero count];
  int fibOneDigits = [fibOne count];
  NSMutableArray*  nextFib = [NSMutableArray arrayWithCapacity:1000];
  NSArray* number;
  int arrayIndex = 999;
  int cellCount = fibZeroDigits - 1;
  int digitZero, digitOne, digitSum;

  // There is an Objective-c loop structure for looping through all objects in array, but stick to this...
  for (int j = 0; j < 1000; j++)
  {
    // All the integers must be zero.
    [nextFib insertObject: [NSNumber numberWithInt:0] atIndex: j];
  }

  for (int i = fibOneDigits; i > 0; i--)
  {
    digitZero = [[fibZero objectAtIndex: cellCount] intValue];
    digitOne = [[fibOne objectAtIndex: i - 1] intValue];
    NSLog(@"arrayIndex is: %i", arrayIndex); // arrayIndex seems correct why am I getting 104?
    if (digitZero + digitOne < 10)
    {
        digitSum = digitZero + digitOne + [[nextFib objectAtIndex: arrayIndex] intValue];
        [nextFib insertObject: [NSNumber numberWithInt:digitSum] atIndex: arrayIndex];
    }
    else
    {
        digitSum = digitZero + digitOne - 10 + [[nextFib objectAtIndex:arrayIndex] intValue];
        // This isn't working the second time, though digitSum is added correctly...
        // Getting 1,0,4 for fibTwelve instead of 144
        // Doesn't work for fibEight get 1,0 instead of 13...
        [nextFib insertObject: [NSNumber numberWithInt:digitSum] atIndex: arrayIndex]; 
        [nextFib insertObject: [NSNumber numberWithInt: 1] atIndex: arrayIndex -1];
    }
    arrayIndex = arrayIndex - 1;
    cellCount = cellCount - 1;
  }
  // Must carry the last digit in fibOne if arrays are of different sizes...

  if (fibZeroDigits < fibOneDigits)
  {
    // fibOne has one extra digit
    digitSum = [[fibOne objectAtIndex:0] intValue] + [[nextFib objectAtIndex:arrayIndex - 1] intValue];
    [nextFib insertObject:[NSNumber numberWithInt:digitSum] atIndex:arrayIndex -1];
  }

  // Shouldn't return nextFib, but only the signifigant, ie non zero integers

  // Find first non zero digit and then the range from there until the end of the array nextFib
  for(int n = 0; n < 1000; n++)
  {
    if ([[nextFib objectAtIndex: n] intValue] > 0)
    {
        // First non zero digit.
        NSRange theRange;

        theRange.location = n;
        theRange.length = 1000 - n;

        number = [nextFib subarrayWithRange:theRange];
        break; // Could set n = 1000 which would also break...
     }
   }


  return number;
}

Any ideas why digitSum and the NSNumber I create with it isn't getting stored as expected when carrying is necessary?

My biggest bug was caused by using insertObjectAtIndex: instead of replaceObjectAtIndex: withObject: but there are other bugs in the code above too. — Muskie, Feb 03 '13 at 19:34
Congratulations, the answer you gave to problem 25 is correct. You are the 60154th person to have solved this problem. — Muskie, Feb 03 '13 at 20:42
I fixed my code then from my main.m ran it until I got the term that was a 1000 digits long. — Muskie, Feb 03 '13 at 20:43

score 1 · Accepted Answer · answered Feb 06 '13 at 20:34

As alluded to above, I found my own bug and several more. insertObjectAtIndex adds an entirely new object to the NSMutableArray, I instead wanted to replaceObjectAtIndexWith which replaced the previous digit with the newly calculated digit.

XCode just updated adding the ability to look inside NSArrays from the debugger which would have been nice as I also mentioned above. Here is the method for adding two 1000 digit numbers, it could be modified to add even larger numbers, they don't have to even be Fibonacci numbers.

+ (NSArray*) nextBigFibonancci: (NSArray*) fibZero After: (NSArray*) fibOne
{    
    int fibZeroDigits = [fibZero count];
    int fibOneDigits = [fibOne count];
    int loops = fibZeroDigits - 1;
    int fibOneIndex = loops;
    NSMutableArray*  nextFib = [NSMutableArray arrayWithCapacity:1000];
    NSArray* number;
    int arrayIndex = 999;
    int digitZero, digitOne, digitSum;

    // There is an Objective-c loop structure for looping through all objects in array, but I'll just stick to this...
    for (int j = 0; j <= arrayIndex; j++) 
    {
        // All the integers start at zero.
        [nextFib insertObject: [NSNumber numberWithInt:0] atIndex: j];
    }

    if (fibOneDigits > fibZeroDigits)
    {
        fibOneIndex++;
    }

    for (int i = loops; i >= 0; i--)
    {
        digitZero = [[fibZero objectAtIndex: i ] intValue];
        digitOne = [[fibOne objectAtIndex: fibOneIndex ] intValue];
        // Have to use replaceObjectAtIndex not insertObjectAtIndex!
        digitSum = digitZero + digitOne + [[nextFib objectAtIndex: arrayIndex] intValue];
        if (digitSum < 10)
        {
            [nextFib replaceObjectAtIndex: arrayIndex withObject: [NSNumber numberWithInt:digitSum]];
        }
        else
        {
            digitSum = digitSum - 10;
            [nextFib replaceObjectAtIndex: arrayIndex withObject: [NSNumber numberWithInt:digitSum]];
            [nextFib replaceObjectAtIndex: arrayIndex -1 withObject: [NSNumber numberWithInt:1]];
        }
        arrayIndex = arrayIndex - 1;
        fibOneIndex = fibOneIndex -1;
    }
    // Must carry the last digit in fibOne if arrays are of different sizes...

    if (fibZeroDigits < fibOneDigits)
    {
        // fibOne has one extra digit
        digitSum = [[fibOne objectAtIndex:0] intValue] + [[nextFib objectAtIndex:arrayIndex] intValue];
        [nextFib replaceObjectAtIndex: arrayIndex withObject: [NSNumber numberWithInt:digitSum]];
    }

    // Shouldn't return nextFib, but only the signifigant, ie non zero integers
    // Find first non zero digit and then the range from there until the end of the array nextFib
    for(int n = 0; n < 1000; n++)
    {
        if ([[nextFib objectAtIndex: n] intValue] > 0)
        {
            // First non zero digit.
            NSRange theRange;

            theRange.location = n;
            theRange.length = 1000 - n;  

            number = [nextFib subarrayWithRange:theRange];
            break; // Could set n = 1000 which would also break...
        }
    }


    return number;
}

score 0 · Answer 2 · answered Feb 02 '13 at 20:41

0

I also used an NSArray of NSNumbers to solve this. You can use much less code if you store the Fibonacci numbers' digits in reverse order.

I created a method with 2 arguments, both NSArrays representing Fibonacci numbers, and it returns an NSArray representing the next number. So, to figure out the 13th Fibonacci number by adding 89 and 144, the methods two arguments' values are [9, 8] & [4, 4, 1], and it returns [3, 3, 2].

I think you'll find it simpler to 'carry the one' this way. Apparently there's also a way to solve this on paper if you're a genius mathematician.

answered Feb 02 '13 at 20:41

John Sauer

4,411
1
25
33

I know my answer is not optimal, it doesn't even work, but I still want to know why when digiSum = 3 in the debugger and I create an NSNumber with digiSum and store it in an NSMutableArray and then take a sub array and return it from this method, my 3 becomes a 0 when I read the NSNumber intValues out? – Muskie Feb 03 '13 at 18:53
Your recent comments on the question say that you solved the problem. Does that mean you've answered your own question and your code is working? – John Sauer Feb 03 '13 at 21:41
My code is working, am I supposed to something more to close the thread? I don't think I have the power. The problem was insertObjectAtIndex added a new object and moved everything left or right, where as replaceObjectAtIndexWith replaced the current zero digit with the one I calculated, but there were other mistakes. Xcode update with the ability to inspect NSArrays and NSMutableArrays which would have helped in debugging this, but I just used NSLog... – Muskie Feb 05 '13 at 18:34
Yup, you can close this by either accepting an answer (even an answer you provide yourself), or deleting the question. Accepting an answer will tell others that they don't need to attempt to solve this question anymore. I'm glad you got it working. – John Sauer Feb 05 '13 at 19:11
I had to Google how to answer a question, luckily there is a discussion thread for that. ;-) – Muskie Feb 06 '13 at 20:35

Unexpected behaviour when inserting object into NSMutableArray

2 Answers2