Ruud H.G. van Tol on Sun, 08 Jan 2023 21:49:39 +0100

 lookup-optimization

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: lookup-optimization
• From: "Ruud H.G. van Tol" <rvtol@isolution.nl>
• Date: Sun, 8 Jan 2023 21:48:29 +0100
• Delivery-date: Sun, 08 Jan 2023 21:49:39 +0100
• Dkim-signature: v=1; a=rsa-sha256; c=simple/simple; d=isolution.nl; s=soverin; t=1673210910; bh=giQhHXpzFxcW7r+eF5CuEOQt6DfwDEPNNtvZqvlJBHM=; h=Date:To:From:Subject:From; b=oZHzDqKvwRU+El98eSlafZNHhOZQZyihPodGLdjbWNLY2IUgxa8C4ffNYF4YR+vjN oBPpvkhprbLxjoT1D8+hbFTC07CcLvn7wwwD1Z/sB1R9PDkkCcCgfQJ5lo0Ka5HCR3 ezPUXNSfoBMB7flTOSktlS05K8AAQlSH1/YYS5p0Unoo4WqW6y8fHUOd5W5Ipo65r1 KsbZQwEOvfi6OBeZKFQGnQn6X4ttgGyNThgZ6xLlnPITrh+65f4/vGYHg1FCW3CsMA UVe7RGKnMkLTBo4cinyhZZ91FPgLMGIEVzFjIsKoQ0cu6zmJnh4ahI33sX8LNnOw/y RqSV5tZ9DVZ3g==

```
In the below code I build up a set 's',
against which I first check each new case
for "congruence".

If no such case was found,
then the new case gets added to the set.

Each element of 's' is a tuple
of a power-of-2 and an offset.

(1) I wonder if Mod() is better for that. Or store the sum?
(2) Would vecsearch() be good to use for this?
(3) Any ideas on doing things differently, are welcome.

-- Greetings, Ruud

- - - - - - - - - - - - - - - - - - -

A243115( N=575, V=0 )= {
my
( r= []  /* result */
, s= []  /* lookup-set */
, t= [ [1,2,1,1], [2,1,1,0] ]  /* detailed table */
);

forstep
( v2= 3, N, 4
, my( found= 0 );
for /* Look up v2-class in s */
( i=1, #s
, if
( s[i][2] == v2 % 2^s[i][1]
, found= 1;
break;
);
);
if( found, next );

my( p2= 0, p3= 0, v3= v2 );
until
( v3 <= v2  /* until drop */
, if
( v3 % 2
, v3+= v3\2 + 1; p3++;
, v3\= 2;
);
p2++;
);
r= concat(r, v2); /* store */
s= Set( concat(s, [ [p2, v2] ]) );
if( 1 < V, t= concat(t, [ [v2, p2, v3, p3] ]) );
);

if
( 1 < V  /* p.table */
, for
( i=1, #t
, my( [v2, p2, v3, p3]= t[i] );
printf
( "%4s + i* 2^%3s -> %4s +i* 3^%3s\n"
, v2, p2, v3, p3
);
);
print("[...]")
);
if( V, print("s=", s) ); /* p.lookup-set */
print("r=", r);  /* p.result */
}

? A243115();  \\ non-verbose run (default)
```
r=[3, 7, 11, 15, 23, 27, 31, 39, 47, 59, 63, 71, 79, 91, 95, 103, 111, 123, 127, 155, 159, 167, 175, 191, 199, 207, 219, 223, 231, 239, 251, 255, 283, 287, 303, 319, 327, 347, 359, 367, 383, 411, 415, 423, 447, 463, 479, 487, 495, 507, 511, 539, 543, 559, 575]
```cpu time = 4 ms, real time = 4 ms.

? A243115( 100, 2 );  \\ verbose run
[...]

? A243115(10^5);
r=[...]
cpu time = 5,156 ms, real time = 5,192 ms.

-o-o-o-o-o-o-o-o-

```