[libre-riscv-dev] div/mod algorithm written in python

[Luke Kenneth Casson Leighton]

On Sat, Jul 20, 2019 at 8:21 AM Jacob Lifshay <programmerjake at gmail.com> wrote:
>
> On Fri, Jul 19, 2019, 23:49 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
> wrote:
>
> > On Sat, Jul 20, 2019 at 6:55 AM Jacob Lifshay <programmerjake at gmail.com>
> > wrote:
> > >
> > > On Fri, Jul 19, 2019, 22:47 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
> > > wrote:
> > >
> > > > how you getting on btw?  (and kazan?)
> > > >
> > > going somewhat slow. I ended up taking a day or two writing an algebraic
> > > number library (https://github.com/programmerjake/algebraics) for later
> > use
> > > in verifying that the different operations round correctly (it can
> > exactly
> > > represent the roots of any polynomial with rational coefficients, which
> > > includes sqrt and rsqrt), but got bogged down in algorithms to factor
> > > polynomials.
> >
> > sounds neat - do keep focussed, though.
> >
> yeah.
>
> btw, do you know any good online references for understanding what
> a Gröbner basis is? it's used to factor polynomials.

 wolfram, and potentially google "groebner site:arxiv.org" ?

> once the factoring algorithm is implemented, the rest (algebraic number
> add/sub/mul/div/rational-powers/floor/ceil/comparison) should be quite
> easy, that way we can write the ieee 754 rounding function once and it will
> work correctly for all the hw fp operations (assuming we don't implement
> exp/log or trig functions, though sinpi/cospi/tanpi will work since
> rational inputs give algebraic outputs), allowing easier systematic testing.

 coool.

> >
> > btw is the div core in a position where it could be plugged in to the
> > FPDIV "stub" code?
> >
> yeah, I am in the middle of building the fp/int interface. the int div/rem
> should be quite easy, just copy the corresponding test. for divu/remu, you
> can just copy the inputs and outputs directly (with shifting to account for
> differing numbers of fractional bits -- see test). fp will be a little
> harder.

yehyeh.  well, the basic routines are all there, already done: there's
pipeline stages already that will shift the mantissa up so that the
MSB is always 1 (and adjust the exponent accordingly as well), and
likewise on the way out.

so as long as the integer "thing" works, fitting it in place is
actually pretty trivial.

once the result is generated, the post-normalisation pipeline stages
take care of re-normalisation, so even if the mantissa (int-result)
doesn't have a MSB which is 1, that's *precisely* what
re-normalisation takes care of: shifting the MSB and adjusting the
exponent as well.

so the exponent will need to be carried through the int-div pipeline
stages *untouched*, ok?  generated/modified by the de-normalisation,
carried through the int-div pipe, handed to the post/re-normalisation,
and dealt with there.

l.