Advanced Search

Question: Boole Mobius Transform Procedure efficiency

Question:Boole Mobius Transform Procedure efficiency

Ronan 802 Maple 2019
performance procedure vector
January 17 2021
0

I have this procedure to perform a Boole-Mobius Transform. I took me quite a while to figure out. Whereas it works, I wonder how it should be done efficiently? The document is also attached which shows the steps I went through to derive the procedure. I can't get the document to display.

BooleMobiusTransform := proc(V) 
local n, im, istep, jm, h, istart, i, j, k; n := ilog2(numelems(V)); im := 2^n/2; istep := im; jm := 1; h := 2^n; 
for k to n do
 istart := 1; 
for j to jm do 
for i from istart to im - 1 + istart do 
V(istep + i) := (V[istep + i] + V[i]) mod 2;
 end do;
 istart := istart + h; 
end do;
 im := 1/2*im; istep := 1/2*istep; jm := 2*jm; h := 1/2*h; 
end do; 
return V; 
end proc

Boole-Mobius_Transform.mw
Please Wait...