gcdext_1 questions

[Niels Möller]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

> you mean you want to determine the best q modulo 2^{j+1}, i.e., the value
> so that |u + q v| is minimal? 

Something like that. Ideally, I'd like to select q to minimize the
"size" of u + q v, where the size excludes zeros both to the right and
to the left, i.e., the "size" of x is log_2 (x) - trailing zeros of x. I'd suspect
that's a hard problem (with complete freedom to eliminate some bots to
the leftf and some bits to the right). The procedure below gives an
approximative solution that eliminates most bits at the right.

There are two, or maybe three steps. Consider the case |u| > |v|.

0. Select the type of range to be used for q, (always positive, always
   negative, or symmetric around zero), depending on the signs of u and
   v. The range is parametrized by j. E.g., we may decide to always use
   |q| < 2^j

1. Select j. j should be as large as possible, under the constraint that
   |u + q v| should be guaranteed to not be much larger than u. This
   means that j should be the difference in bit size betwen u and v
   (give or take a bit or two depending on the decision in step 0).

2. Select q, in the given range from step 0, which cancels as many bits
   as possible at the least significant end. E.g., with |q| < 2^j, we
   find a q which cancels at least j+1 bits.

> I'm not sure to understand your code, since j is not defined that way in our
> algorithm. Do you mean a variant of our algorithm?

Yes, It's a slightly different algorithm, choosing j in a different way.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.