Some basic questions on the invert_limb code

Torbjorn Granlund tg at gmplib.org
Mon Nov 18 20:41:38 UTC 2013


I think we have already asked you to not cross-post to multiple lists.
Please respect our rules, or do not post at all.

  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..?
  
That depends on which file you're looking at.

Newer code (such as the arm64 invert_limb.asm) presumaby uses the method
suggested in the paper "Improved division of Invarant Integers", i.e.,
floor(0x7fd00/i) for index i.  The newer tables are computed at compile
time.

Older code uses various other variants, with poor documentation.

-- 
Torbjörn


More information about the gmp-discuss mailing list