[Libre-soc-bugs] [Bug 1155] O(n^2) multiplication REMAP mode(s)

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=1155

--- Comment #18 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #16)
> oo hang on, i have my head round this now :) so i have a question:
> at the cross-over point to move to the next row (the outer loop)
> is it *guaranteed* that ca=0 such that it will not interfere with
> the new row?

yes afaict. I did an exhaustive check for word sizes of 2 bits and 3-word by
3-word multiplication (code below), so this formally proves that case. I have
no reason to think that doesn't extend to more words and/or bigger words, so it
should work.

exhaustive check code (not pretty, but works):

>>> def maddedu(a, b, c): return (a*b+c)%4,(a*b+c)//4
... 
>>> def adde(a,b,c): return (a+b+c)%4,(a+b+c)//4
... 
>>> def mul(a,b):
...  y=[0]*(len(a)+len(b))
...  ca=0
...  for ai in range(len(a)):
...   for bi in range(len(b)):
...    y[ai+bi],t=maddedu(a[ai],b[bi],y[ai+bi])
...    y[ai+bi+1],ca=adde(y[ai+bi+1],t,ca)
...  return y
... 
>>> def i2l(v,l): return [(v >> (i * 2)) % 4 for i in range(l)]
... 
>>> def l2i(l): return sum(v << (i * 2) for i, v in enumerate(l))
... 
>>> for a in range(64):
...  for b in range(64):
...   expected = a * b
...   v = l2i(mul(i2l(a,3),i2l(b,3)))
...   assert expected == v
... 
>>>

-- 
You are receiving this mail because:
You are on the CC list for the bug.