Re: forbidden comparison

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

On 2022-01-20 01:05, Kevin Ryde wrote:
> "Ruud H.G. van Tol" <rvtol@isolution.nl> writes:

> > my( v= 23, c3= 7);
> > \\ ...
> > my( c= c3 * 2 ); while( c < v, c3= c; c*= 2 ); \\un-oddify
> > What are alternative ways to do such?
>
> Logs can give you k shift either right or 1 too big, and compare to see
> which.
>
> k = logint(v,2) - logint(c3,2)
> c3 <<= k;
> if(c3 >= v, c3>>=1)

Thanks Kevin, so obvious once you see it,
must have been there already
and then getting ignored for years.
It looks expensive, so I need to benchmark.


To show more visually:

|__|__|__|__|__|__|16|
|__|__|__|__|__|40|_8|
|__|28|__|__|52|20|_4|
|__|14|22|34|26|10|_2|
| 9|_7|11|17|13|_5|_1|

For example from 7 to 5,
or rather from 11 to 10:

c3 = c2 = 11;  \\ odd > 1
p2 = 0;
p3 = 0;

while
( c3 >= c2
, c3 = 3 * c3 + 1;
  p3 += 1;
  vc3 = valuation( c3, 2 );
  c3 /= vc3;
  p2 += vc3;
);

So now c3 can end up too small,
and need a doubling correction,
with p2 kept in sync.

This trades one while-loop for another.
Either do the halving until done,
or divide by the valuation(),
and go back up if needed.

This is all about deriving
the "optimal" instances of:

  2^p2 * i + c2 -> 3^p3 * i + c3

I'll also try this on an "(odd - 1) / 2" map.

-- Greetings, Ruud