Mou Code

-- source -- -- polynomial evaluation without broadcast, Mou 1991 Algo.4.8 -- -- Each element starts with its own a*x, then at each level of correspondence is enhanced: -- It scales by the predecessor-group's tail power and it adds the predecessor-group's tail sum -- Then also simultaneously project and record the new-group sum and new-group power. xval = 2 basef(a,x) = (me=a*x,last=a*x,pwr=x) -- 0th node: (me=last=a0*1,pwr=1), 1st node (a1*x^1,x^1) left ( (meL,lastL,pwrL), (meR,lastR,pwrR) ) = ( meL , (lastL+lastR*pwrL), pwrL*pwrR) right ( (meR,lastR,pwrR), (meL,lastL,pwrL) ) = (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) loc = (!left, !right) poly_dc = PDC(d_lr,c_lr,id, loc @ # ! corr, atomq, lift1(basef)) polynob = unzip.0 @ poly_dc @ zip randAs = [1,1,1,1,1,1,1,1] -- was shuffled(2) Xs = [1] + xvec(xval, 7) -- vector join: + trace(polynob, randAs, Xs) -- polynob( [1,1,1,1], [1,2,2,2 ] ) should result in [1,3,7,15 ] -- polynob( [1,1,1,1,1,1,1,1], [1,2,2,2,2,2,2,2] ) should result in [1,3,7,15,31,63,127,255] -- end source -- -- trace: polynob([1,1,1,1,1,1,1,1], [1,2,2,2,2,2,2,2]) -- _zip -> [(1, 1),(1, 2),(1, 2),(1, 2),(1, 2),(1, 2),(1, 2),(1, 2)] poly_dc([(1, 1),(1, 2),(1, 2),(1, 2),(1, 2),(1, 2),(1, 2),(1, 2)]) divide d_lr -> ([(1, 1),(1, 2),(1, 2),(1, 2)], [(1, 2),(1, 2),(1, 2),(1, 2)]) poly_dc([(1, 1),(1, 2),(1, 2),(1, 2)]) divide d_lr -> ([(1, 1),(1, 2)], [(1, 2),(1, 2)]) poly_dc([(1, 1),(1, 2)]) divide d_lr -> ([(1, 1)], [(1, 2)]) poly_dc([(1, 1)]) ⇣ atom; basef -> [(1, 1, 1)] poly_dc([(1, 2)]) ⇣ atom; basef -> [(2, 2, 2)] post #!corr -> ([((1, 1, 1), (2, 2, 2))], [((2, 2, 2), (1, 1, 1))]) left(((1, 1, 1), (2, 2, 2))) [meL=1, lastL=1, pwrL=1, meR=2, lastR=2, pwrR=2] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 1 , (1+2*1), 1*2) right(((2, 2, 2), (1, 1, 1))) [meR=2, lastR=2, pwrR=2, meL=1, lastL=1, pwrL=1] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (1+2*1, (1+2*1), 1*2) post (!left, !right) -> ([(1, 3, 2)], [(3, 3, 2)]) combine c_lr -> [(1, 3, 2),(3, 3, 2)] poly_dc([(1, 2),(1, 2)]) divide d_lr -> ([(1, 2)], [(1, 2)]) poly_dc([(1, 2)]) ⇣ atom; basef -> [(2, 2, 2)] poly_dc([(1, 2)]) ⇣ atom; basef -> [(2, 2, 2)] post #!corr -> ([((2, 2, 2), (2, 2, 2))], [((2, 2, 2), (2, 2, 2))]) left(((2, 2, 2), (2, 2, 2))) [meL=2, lastL=2, pwrL=2, meR=2, lastR=2, pwrR=2] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 2 , (2+2*2), 2*2) right(((2, 2, 2), (2, 2, 2))) [meR=2, lastR=2, pwrR=2, meL=2, lastL=2, pwrL=2] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (2+2*2, (2+2*2), 2*2) post (!left, !right) -> ([(2, 6, 4)], [(6, 6, 4)]) combine c_lr -> [(2, 6, 4),(6, 6, 4)] post #!corr -> ([((1, 3, 2), (2, 6, 4)),((3, 3, 2), (6, 6, 4))], [((2, 6, 4), (1, 3, 2)),((6, 6, 4), (3, 3, 2))]) left(((1, 3, 2), (2, 6, 4))) [meL=1, lastL=3, pwrL=2, meR=2, lastR=6, pwrR=4] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 1 , (3+6*2), 2*4) left(((3, 3, 2), (6, 6, 4))) [meL=3, lastL=3, pwrL=2, meR=6, lastR=6, pwrR=4] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 3 , (3+6*2), 2*4) right(((2, 6, 4), (1, 3, 2))) [meR=2, lastR=6, pwrR=4, meL=1, lastL=3, pwrL=2] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (3+2*2, (3+6*2), 2*4) right(((6, 6, 4), (3, 3, 2))) [meR=6, lastR=6, pwrR=4, meL=3, lastL=3, pwrL=2] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (3+6*2, (3+6*2), 2*4) post (!left, !right) -> ([(1, 15, 8),(3, 15, 8)], [(7, 15, 8),(15, 15, 8)]) combine c_lr -> [(1, 15, 8),(3, 15, 8),(7, 15, 8),(15, 15, 8)] poly_dc([(1, 2),(1, 2),(1, 2),(1, 2)]) divide d_lr -> ([(1, 2),(1, 2)], [(1, 2),(1, 2)]) poly_dc([(1, 2),(1, 2)]) divide d_lr -> ([(1, 2)], [(1, 2)]) poly_dc([(1, 2)]) ⇣ atom; basef -> [(2, 2, 2)] poly_dc([(1, 2)]) ⇣ atom; basef -> [(2, 2, 2)] post #!corr -> ([((2, 2, 2), (2, 2, 2))], [((2, 2, 2), (2, 2, 2))]) left(((2, 2, 2), (2, 2, 2))) [meL=2, lastL=2, pwrL=2, meR=2, lastR=2, pwrR=2] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 2 , (2+2*2), 2*2) right(((2, 2, 2), (2, 2, 2))) [meR=2, lastR=2, pwrR=2, meL=2, lastL=2, pwrL=2] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (2+2*2, (2+2*2), 2*2) post (!left, !right) -> ([(2, 6, 4)], [(6, 6, 4)]) combine c_lr -> [(2, 6, 4),(6, 6, 4)] poly_dc([(1, 2),(1, 2)]) divide d_lr -> ([(1, 2)], [(1, 2)]) poly_dc([(1, 2)]) ⇣ atom; basef -> [(2, 2, 2)] poly_dc([(1, 2)]) ⇣ atom; basef -> [(2, 2, 2)] post #!corr -> ([((2, 2, 2), (2, 2, 2))], [((2, 2, 2), (2, 2, 2))]) left(((2, 2, 2), (2, 2, 2))) [meL=2, lastL=2, pwrL=2, meR=2, lastR=2, pwrR=2] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 2 , (2+2*2), 2*2) right(((2, 2, 2), (2, 2, 2))) [meR=2, lastR=2, pwrR=2, meL=2, lastL=2, pwrL=2] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (2+2*2, (2+2*2), 2*2) post (!left, !right) -> ([(2, 6, 4)], [(6, 6, 4)]) combine c_lr -> [(2, 6, 4),(6, 6, 4)] post #!corr -> ([((2, 6, 4), (2, 6, 4)),((6, 6, 4), (6, 6, 4))], [((2, 6, 4), (2, 6, 4)),((6, 6, 4), (6, 6, 4))]) left(((2, 6, 4), (2, 6, 4))) [meL=2, lastL=6, pwrL=4, meR=2, lastR=6, pwrR=4] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 2 , (6+6*4), 4*4) left(((6, 6, 4), (6, 6, 4))) [meL=6, lastL=6, pwrL=4, meR=6, lastR=6, pwrR=4] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 6 , (6+6*4), 4*4) right(((2, 6, 4), (2, 6, 4))) [meR=2, lastR=6, pwrR=4, meL=2, lastL=6, pwrL=4] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (6+2*4, (6+6*4), 4*4) right(((6, 6, 4), (6, 6, 4))) [meR=6, lastR=6, pwrR=4, meL=6, lastL=6, pwrL=4] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (6+6*4, (6+6*4), 4*4) post (!left, !right) -> ([(2, 30, 16),(6, 30, 16)], [(14, 30, 16),(30, 30, 16)]) combine c_lr -> [(2, 30, 16),(6, 30, 16),(14, 30, 16),(30, 30, 16)] post #!corr -> ([((1, 15, 8), (2, 30, 16)),((3, 15, 8), (6, 30, 16)),((7, 15, 8), (14, 30, 16)),((15, 15, 8), (30, 30, 16))], [((2, 30, 16), (1, 15, 8)),((6, 30, 16), (3, 15, 8)),((14, 30, 16), (7, 15, 8)),((30, 30, 16), (15, 15, 8))]) left(((1, 15, 8), (2, 30, 16))) [meL=1, lastL=15, pwrL=8, meR=2, lastR=30, pwrR=16] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 1 , (15+30*8), 8*16) left(((3, 15, 8), (6, 30, 16))) [meL=3, lastL=15, pwrL=8, meR=6, lastR=30, pwrR=16] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 3 , (15+30*8), 8*16) left(((7, 15, 8), (14, 30, 16))) [meL=7, lastL=15, pwrL=8, meR=14, lastR=30, pwrR=16] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 7 , (15+30*8), 8*16) left(((15, 15, 8), (30, 30, 16))) [meL=15, lastL=15, pwrL=8, meR=30, lastR=30, pwrR=16] -> ( meL , (lastL+lastR*pwrL), pwrL*pwrR) = ( 15 , (15+30*8), 8*16) right(((2, 30, 16), (1, 15, 8))) [meR=2, lastR=30, pwrR=16, meL=1, lastL=15, pwrL=8] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (15+2*8, (15+30*8), 8*16) right(((6, 30, 16), (3, 15, 8))) [meR=6, lastR=30, pwrR=16, meL=3, lastL=15, pwrL=8] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (15+6*8, (15+30*8), 8*16) right(((14, 30, 16), (7, 15, 8))) [meR=14, lastR=30, pwrR=16, meL=7, lastL=15, pwrL=8] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (15+14*8, (15+30*8), 8*16) right(((30, 30, 16), (15, 15, 8))) [meR=30, lastR=30, pwrR=16, meL=15, lastL=15, pwrL=8] -> (lastL+meR*pwrL, (lastL+lastR*pwrL), pwrL*pwrR) = (15+30*8, (15+30*8), 8*16) post (!left, !right) -> ([(1, 255, 128),(3, 255, 128),(7, 255, 128),(15, 255, 128)], [(31, 255, 128),(63, 255, 128),(127, 255, 128),(255, 255, 128)]) combine c_lr -> [(1, 255, 128),(3, 255, 128),(7, 255, 128),(15, 255, 128),(31, 255, 128),(63, 255, 128),(127, 255, 128),(255, 255, 128)] _unzip.0 -> [1,3,7,15,31,63,127,255] -- result: [1,3,7,15,31,63,127,255] --