[ 2 posts ] 
 Exercise [16.15] 
Author Message

Joined: 22 Apr 2010, 15:52
Posts: 43
Location: Olpe, Germany
Post Exercise [16.15]
My solution:
Exercise_16_15.pdf [19.87 KiB]
Downloaded 170 times

28 Aug 2010, 10:01

Joined: 12 Jul 2010, 07:44
Posts: 154
Post Re: Exercise [16.15]
While numerically valid, JBeckmann's solution suffers from the problem that the code itself depends on n, which is supposed to be an input to the program. (Because of the FOR..NEXT loops nested n levels deep).

It's true that some programming languages support the kind of on-the-fly compilation features that could be used to implement such an algorithm as written, but it's not an elegant way to solve the problem!

Here's a different pseudocode algorithm that makes use of recursion rather than nested loops, and also orders the squares lowest to highest to avoid checking permutations of the same set of squares:


// Return the smallest integer that cannot be formed as the sum of n squares:

FUNCTION findSmallestNonSumNSquares(n)
    IF (n<1) THEN RETURN 1           // n=0 is a special case
    i <- 1
        IF (NOT isSumofNSquares(i, n, 0, 0)) THEN RETURN i
        i <- i+1

// Return TRUE if k can be formed as the sum of n squares, FALSE if not:
// NOTE: v is the lowest value whose square we need to check,
//       and s=v*v is passed in just to avoid computing it.
// NOTE: All arguments are local variables, so a "new" set of k, n, v, and s is used at each recursion.

FUNCTION isSumofNSquares(k, n, v, s)
    IF (n=1) THEN RETURN (k is a perfect square)   // i.e. TRUE if k is a perfect square, FALSE if not
    m <- INTEGER PART OF (k/n)                     // maximum square we'll need to check
        IF (isSumofNSquares(k-s, n-1, v, s)) THEN RETURN TRUE
        v <- v+1
        s <- s+2v-1                                // = v*v
    UNTIL (s>m)

It'd be more intuitive to write s <- v*v to compute the square, but calculating s <- s+2v-1 is faster.

I haven't specified how to check a value k to see if it's a perfect square; you could just check whether the square root is an integer, but there may be faster ways to do it.

The memory requirements of this algorithm are O(n).

Significant optimization could be achieved by rewriting the algorithm to maintain a cache of the minimum number of squares needed to sum to each successive value: 1 (1 square), 2 (2 squares), 3 (3 squares), 4 (2 squares), ...etc, adding one entry to the cache at each iteration of the main loop in 'findSmallestNonSumNSquares'. However, using this optimization trades memory for speed, and means that memory usage would increase indefinitely as the program checks progressively higher and higher numbers for non-existent (when n>3) solutions.

09 May 2011, 17:53
   [ 2 posts ]