Five programming problems every Software Engineer should be able to solve in less than 1 hour

[Geoff Canyon]

On Sat, May 9, 2015 at 7:12 PM, Jerry Jensen <jhj at jhj.com> wrote:

> We went through this a while ago, I think a challenge forwarded by Mark
> Wieder. The problem is that integers overflow and start giving wrong
> answers part way to 100. I forget the exact place it happens.
>
> I wrote a few that did it the hard way (character by character arithmetic)
> - I’ll see if I can find them.
>

Ha, I totally didn't think about overflow -- I fail :-)

Here's a version that I think works. At least the result matches entries
for the value on the web:

function fib N
   put "0,1" into R
   if N <= 2 then return item 1 to N of R
   put 0 into F1
   put 1 into F2
   repeat N - 2
      put bigAdd(F1,F2) into F3
      put "",F3 after R
      put F2 into F1
      put F3 into F2
   end repeat
   return R
end fib

function bigAdd X,Y
   put 0 into C
   repeat
      if X is empty and Y is empty and (C is empty or C=0) then exit repeat
      put "00000000000000" & ((char -14 to -1 of X) + (char -14 to -1 of Y)
+ C) into RT
      put char -14 to -1 of RT before R
      put 0 + char 1 to -15 of RT into C
      delete char -14 to -1 of X
      delete char -14 to -1 of Y
   end repeat
   repeat
      if R is empty or (R = 0 and length(R) = 1) or char 1 of R <> 0 then
return R
      delete char 1 of R
   end repeat
end bigAdd