Re: lookup-optimization

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, Jan 08, 2023 at 11:46:55PM +0100, Karim Belabas wrote:
> A243115(N = 575) =
> { my(r= [], s= Map());
>   forstep(v2 = 3, N, 4,
>     my(found = 0);
>     for (i = 1, #s,
>       if (valuation(s[i][2] - v2, 2) >= s[i][1], found = 1; break));
>     if (found, next);
> 
>     my(p2 = 0, v3 = v2);
>     until (v3 <= v2,
>       if (bitand(v3,1), v3 += v3 >> 1 + 1;
>                       , v3 >>= 1);
>       p2++);
>     r = concat(r, v2);
>     s = mapput(~s, v2,p2));
>   r;
> }

By merging with my version I get

A243115(N = 575) =
{ my(r= List(), s= Map());
  forstep(v2 = 3, N, 4,
    for(i=1,logint(v2,2)+1,
      my(nv2=v2%2^i,p2);
      if (mapisdefined(s,nv2,&p2) && nv2==v2%2^p2, next(2)));
    my(p2 = 0, v3 = v2);
    until (v3 <= v2,
      if (bitand(v3,1), v3 += v3 >> 1 + 1;
                      , v3 >>= 1);
      p2++);
    listput(~r, v2);
    mapput(~s, v2,p2));
  Vec(r);
}

? A243115(10^5);
  ***   last result computed in 168 ms.
? A243115(10^6);
  ***   last result computed in 1,936 ms.

(concat is very slow!)

Cheers,
-- 
Bill Allombert
Ingénieur en calcul scientifique ❄
CNRS/IMB UMR 5251