Re: [Fastlibnt-devel] Scalar multiplication

[William H. <ha...@ya...>]

OK, the naieve scalar multiplications by a single limb
are now done, including test code.

Probably scalar_div_exact_ui/si are next. 

I will implement my trick in the case where the output
polynomial has the same number of limbs per
coefficient as the input polynomial, or where the
input and output polynomials coincide. It doesn't make
a whole load of sense to implement it elsewhere.

Probably for scalar multiplications and exact
divisions by larger operands it makes more sense to
implement my idea everywhere. But at least we can time
it and see what it saves when I get the single limb
version working.

Bill.

--- William Hart <ha...@ya...> wrote:

> 
> --- David Harvey <dmh...@ma...> wrote:
> 
> > 
> > On Apr 25, 2007, at 8:29 PM, William Hart wrote:
> > 
> > > I wonder how much more efficient GMP is at
> > dividing a
> > > 1000 limb integer by a single limb than it is
> > > multiplying 100 x 10 limb integers by the same
> > single
> > > limb. I've got a feeling there is not a lot in
> it,
> > > since there isn't really a better way of
> dividing
> > a
> > > long integer by a single limb than to just
> divide
> > each
> > > limb by that integer and move on, I suppose.
> > 
> > Whoah. GMP definitely does *not* "divide each limb
> > by that integer  
> > and move on". On almost every architecture it uses
> a
> > multiply-by- 
> > inverse. It's much much faster than doing hardware
> > division. They  
> > basically do two hardware multiplies per limb
> > instead of one hardware  
> > division. Granlund (and someone else) wrote a
> whole
> > paper on how this  
> > is done in GMP. I think they even do it for
> > multi-limb divisors.
> 
> Right, so presumably it does make sense to try my
> idea
> at some point then.
> 
> > 
> > > Multiplying by an inverse seems out of the
> > question.
> > 
> > Why? GMP does it all over the place.
> 
> Oh, I meant at the C level. Of course they will be
> doing it at a lower level, so I think it will be
> fast
> there.
> 
> > 
> > > Speaking of writing the basics, as we were, are
> > you
> > > planning on working on _Zpoly any more? You
> could
> > > fairly easily implement _Zpoly_scalar_mul_ui and
> > the
> > > like, so I can test against them.
> > 
> > I am... but I am deep in the middle of two other
> > things. One is an  
> > algorithm/paper that is completely
> FLINT-unrelated.
> > (Actually that's  
> > not true. I will need to multiply large
> polynomials,
> > and I might well  
> > try plugging in FLINT instead of NTL when I have
> it
> > all working, as a  
> > very interesting field test.) The second is that
> > ssfft upgrade. If I  
> > stop working on the ssfft thing right now I'll
> > forget everything I  
> > was doing, it's really fiddly stuff. I want to at
> > least get the  
> > forward FFTs done and merged into the trunk. While
> > juggling these two  
> > I don't have time to work on Zpoly for the moment.
> 
> OK, I'll just compare all the coefficients of my
> mpz_format polynomials. That should be fine, though
> in
> effect I am just implementing a version of the
> Zpoly_scalar_mul_ui in the mpn test code. But that
> is
> fine. You can rip it off when you get to that part,
> because I am quite certain it'll save you time since
> it is such a complex algorithm. It'll definitely
> save
> you writing a python prototype. :-)
> 
> Bill.
> 
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam
> protection around 
> http://mail.yahoo.com 
> 
>
-------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2
> express and take
> control of your XML. No limits. Just data. Click to
> get it now.
> http://sourceforge.net/powerbar/db2/
> _______________________________________________
> Fastlibnt-devel mailing list
> Fas...@li...
>
https://lists.sourceforge.net/lists/listinfo/fastlibnt-devel
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com