If we consider that the largest square that has to be looked up in method 1 is ((a+b)/2)2 and in method 2, a2 (if a is the larger of the two), it’s clear that method 1 will require a smaller square table but more operations per run, so there’s some tradeoff involved there.
I’m making an assumption here as I don’t know about general cases for binary subtraction but I think that addition or subtraction of 2 n-digit numbers is O(n·k) while multiplication is definitely O(n2).
Considering binary numbers, 11111111·10101010 will take n2 + 2n - 1 operations (New Turing Omnibus p168).
Substituting into method 2:
If each lookup is one operation (and there is a fixed number of lookups and subtractions for the general case) and subtraction is O(n·k), and division by 10 (i.e. by 2) is also O(n·k) (another assumption - I suppose that since we’re dealing with a fixed denominator unlike the multiplication case where it seemed logical for it to be O(n2)) then I think the function increases as n·k.
But it requires a square table. A LARGE ONE. However, this may be okay because you can reuse the squares in many calculations so perhaps in the long run it somehow balances out the initial deficit?
Or maybe the table can be populated as you go so there’s no initial deficit but a general inefficiency which soon disappears as the table values start getting filled in?
I really don’t know though.
It’s a nice thought.
Hmm?
Pax
Recent Comments