Project 4 Tips and Corrections
  1. The binary numbers for M1, M2, and M in the examples at the end of part II were incorrect. They have been corrected on the page now.

  2. The addArray and subArray static methods in the PosInt class will be helpful to you in implementing Karatsuba's algorithm. But there is some confusion as to how they work.

    Basically, the len argument is the length of the second array. The length of the first array (destination) is essentially assumed to be infinite. That's what it means to say that "REQUIREMENT: dest has enough space to hold the complete sum". The consequence is that the carries will be propogated as far as necessary, even potentially off the end of the first array if it is not large enough.

    For example if you had A=[4,7,9,9,6] and B=[7,7], then calling 

    addArray(A,B,2)
    would result in A=[1,5,0,0,7]. This corresponds to the addition of 69974 + 77 = 70051.

    Notice that the carry goes all the way to the last digit in A even through the length of B (and the argument) is just 2.

    What this means is that if you allocate extra space in your result array to store the carry (which is a good idea!), this does not mean that you need to also increase the length argument to these helper functions. The carry will automatically go out as far as it needs to in the result array.

  3. Resist the temptation to use the convert() method excessively, as this will give incorrect output if called on large integers. You should only use conver() when you know for sure that the integer you're converting is less than 231.
  4. If something is not working correctly, try to find the smallest example where it doesn't work. Testing is the way you find bugs in your code, and it's most effective when you can test on a small example where you can check the computer's work by hand.