Some basic questions on the invert_limb code

[Anil Singhar]

Some further elucidation on my previous query regarding invert_limb
implementation.

So essentially, I am trying to understand
(i) what procedure was adopted to develop the approximation table used in
the invert_limb function and what do the table entries represent..?
OR
(ii) in other words, what is the relation between the index and the table
entry..?

Following the article and papers I tried to understand the table in the
following way:

1. The table containing 256 entries represent the pre-computed reciprocal
of a normalized 10-bit real number (which is formed out of the 10 MSBs of
the divisor, d). In both the C implementation and the ARM implementation I
saw there are 256 entries, though the algorithms 2 (for 64 bit) and 3 (for
32 bit) use 9 MSBs and 10 MSBs respectively.

2. Assuming that 9 MSBs are used, the first step is to obtain this first
approximation by subtracting 0x100 (per the C implementation) since the the
MSB is set (normalized) so we need only 256 entries. Subtracting 0x100 to
get index is explained by the fact the MSB (8th bit) is set.

3. the range of input to the table as indicated by the index is 256 through
511, which correspond to 1.0000000 through 1.1111111.
4. Assuming my understanding so far is correct, is the table entry
reciprocal of the real numbers 1.0000000 through 1.1111111..?

Apologies for asking these naive questions in the experts forum. Thank you
in advance.

Thanks and Regards,
Anil



On 18 November 2013 17:01, Anil Singhar <anil.singhar at linaro.org> wrote:

> Hi,
>
> I have some basic questions on the mpn_invert_limb function implementation
> which I am trying to understand.
>
> 1. What does the table "approx_tab" represent?
> 2. Why is the content of this table is different between the assembly
> implementation under ARM (i.e. mpn/arm/invert_limb.asm) and the one written
> in C under mpn/cray/ieee/invert_limb.c
>
> Is there any place where this code and the algorithm is explained. I have
> gone through the paper "Improve Division by Invariant Integers" already,
> but still can't follow the code and how and why it is written this way. I
> was hoping to understand the arm assembly implementation from the C
> implementation but that didn't help.
>
> Thanks for reading my mail.
>
> Regards,
> Anil
>
>