divappr or approximate fraction (a diversion from sqrt...)

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   When I looked into sqrt some months ago, I found that it would be nice
>   with a divappr function which didn't require the low mostly
>   uninteresting dividend limbs as input, a bit similar to bdiv_q.
>   
>   Maybe one shouldn't think about that as an approximate division, but
>   rather as an approximate fraction. I've implemented one variant (see
>   below), which takes as input two n limb numbers U and D, with D
>   normalized. 
>   
> This is akin to good old mpn_tdiv_qr with its extra-limb argument which
> we never actually allowd to be != 0.  I like the idea to provide the
> fraction thing separately.

And then the fraction function could perhaps require that U < D, so
there's no non-fraction bit.

> Depending on submul_1c is a bit of a practical problem, since it not
> available in general.  We also lag in implementing addmul_1c (and lack
> completely e.g. addmul_2c).

I think it would make sense to make addmul_1c and submul_1c supported
and public (we discussed a while ago how to do the C versions, if we can
get away with only the _1c functions, and let the public _1 calls be via
a macro or function wrapper calling _1c with zero. In effect, _1c would
be the mandatory function, and a cheaper _1 entry point would be
optional). But I understand it's going to be some non-trivial work. I
had a quick look at implementing _1c for coreihwl, but it wasn't obvious
to me which register held the recurrency limb. 

Not sure about _2c functions.

> Long ago I looked into using addmul_1 for plain division (not bdiv);
> that would speed up things and also simplify low-level code.  We might
> want to look into that again.

Say U is n limbs, and U' is the complement, B^n-1 - U. Then R = U -
QD < D is the remainder, we have

  U' + QD = B^n - 1 - R 

Is that the trick you've been considering? Complement U up front, then
add multiples of D in school-book-style to "eliminate" high limbs by making them equal
to B-1. This produces an R', which is the complement of the remainder.

Regards,
/Niels

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