[Libre-soc-bugs] [Bug 1044] SVP64 implementation of pow(x,y,z)

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=1044

--- Comment #31 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #27)
> > Therefore, I think I should implement Knuth's algorithm D instead of the
> > shift & subtract divmod algorithm we currently have, since I expect it to
> > run 20-50x faster.
> 
> yes i concur. nice thing is, that is a fixed (small) task.

sounds good!
> 
> can i ask you a favour: make it "adaptable" i.e. parameteriseable
> as to what input output and temp regs are used, as well as their
> dimensions? (default to the ones you are using)?

afaict that needs a register allocator, which is the whole rabbit hole i went
down for several months.
> 
> or, if that is a lot of work, just specify the size (bitlength)
> of X and Y?
> 
> the reason i ask is that it becomes possible to crank down the
> sizes to run in sane times.

the crazy times are because shift-sub-based divmod is O(num_bits) and powmod is
O(divmod_time * num_bits) which is 256^2 == 65536 -- huge. knuth's algo-D is
O(num_words^2) which is 4^2 == 16, combined with powmod gives 256 * 4^2 ==
4096, which is doable.
> 
> we do *not* want people running tests to find that it is 300 minutes
> to completion,

with knuth's algo-D, i expect each 256-bit divmod to be <100 operations
runtime, so powmod should be testable with a few min runtime.

> when if we put this in front of a customer for a demo
> (which is actually going to happen) it is ok to say "this is a 128 bit
> powmod, it completes quick but you get the idea".
> 
> 192 bits is.... 3 64-bit GPRs which is more than enough to show
> carry-rollover. am tempted to suggest 128 but it is only 2 GPRs,
> i feel happier with 3 (like in the bigint shift/mul/div tests i wrote)

we really need > 128-bit, since algo-D has some special cases that aren't ever
hit with just two words and maybe not three. 256-bit isn't very big.

-- 
You are receiving this mail because:
You are on the CC list for the bug.