Here's a fft method, it doesn't work with 1e9 bases, but with 10000 base (same
as internal J) it does with a lot of fiddling:
there is a function in misc/numeric.ijs called clean, which I think is supposed
to help with converting from imaginary, but I don't really get it.
require '~addons/math/fftw'
xtoa5 =: (10 }. _4 ,@:((_2&ic)\) 1 (3!:1) ])"0
1000000x p.~ x: 0.1 <.@+ ifftw ([: */@:(fftw"_1) [ }:@,], 0 ,:@#~ <:@+&#)~
xtoa5 1231231232342348209348203492039482341233x
It would take a really huge number of digits before n logn on 4tuples is less
than a fast C with n^2 on 9tuples.
at 340 digits, my approach stays 5 times faster than just *, and there is no
need to evaluate the polynomial to return the integer result.
----- Original Message -----
From: Henry Rich <henryhr...@nc.rr.com>
To: programm...@jsoftware.com
Cc:
Sent: Tuesday, August 25, 2015 7:21 PM
Subject: Re: [Jprogramming] Some extended integer types with math operations
There is definitely faster multiplication code, based on FFT. Roger
worked on it for a while & as I understand it worked, but was never
released.
Henry Rich
On 8/25/2015 6:05 PM, 'Pascal Jasmin' via Programming wrote:
> xtoa =: ([ (-@[ |.@:(0&".@:|.\)&.> <@|.@]) ":@:])"0 NB. dyad
> xtoa9 =: >^:(1=#)@:(9&xtoa)
> atox =: (0 ". 'x' ,~ [: ; ": each)"1
>
> NB.list of extended ints to binary. Uses bit31 to indicate last number.
> Also stores var 32/64bit ints
> xatobN =: (([: ; (2 ic }:@] , (1000000000) + {:@])each)) NB. call with
> @xtoa9 to go direct from xint. positive extended ints only.
> xatobZ =: (([: ; (2 ic }:@] , (1000000000 * *@{:@]) + {:@])each)) NB.
> modified to allow negatives.
> btoxaN =: ([: (}: , (1000000000) -~ {:)each 1000000000 (] <;.2~ <) [: , _4
> (_2&ic)\ ])
> btoxaZ =: ([: (}: , (1000000000 * *@{:) -~ {:)each 1000000000 (] <;.2~ (<|))
> [: , _4 (_2&ic)\ ])
>
>
>
> All of the above are one liners. The main motivation was to create a quick
> and compact storage method for lists of extended ints. It works for lists of
> ints of any size including 32 to 64 bit range, and so is compatible for
> storing lists to be read by either 32 or 64 bit versions of J.
>
> aar =.
> 9876878623423422342342342342034820934203948203948229837429384729348723948723948273492837429384729384727394870394820349820349820348x
>
> xtoa9 aar
> 9876 878623423 422342342 342342034 820934203 948203948 229837429 384729348
> 723948723 948273492 837429384 729384727 394870394 820349820 349820348
>
> simply makes a list of ints in base 1e9. xtoa9r reverses them, which keeps
> them in useful form for several operations, and as lists of ints with fills.
>
> The xatobN and btoxaN functions make a binary string from the list of ints
> (The Z versions support negative ints). Its quicker and/or much smaller than
> other methods.
>
> a =. 2147483304598340953804093234 234234 434332323 248203948203498203492
> 83049283402394820
> 12301928310298310293810293810293810293810293881301982301928310239839482039482834825
> 112312 1 0 29348239429384729347293874293870923409283498647x
>
> # xatobN@:xtoa9 a
> 120
>
> this stores the list without any item counts. An unused bit in the last
> number of a field indicates whether it is the last item in "its" list.
>
> for comparison,
>
> # 3!:1 a
> 1000
>
> While it would be slightly smaller to store bytes, along with a leading count
> (if under 256 byte long integers), it would be much slower with the count
> offset, and that alternative is already slow without tracking counts.
> Roundtrip comparison:
>
> 10 timespacex '256x #. every a.&i. each (3!:2) 3!:1 {&a. each 256#.inv
> each a'
> 0.000643872 211840
>
>
> 10 timespacex 'atox every btoxaN xatobN@:xtoa9 a'
> 0.000176384 13056
>
>
> 4 times faster and low memory. And leaving it boxed is 5 times the size.
>
> # 3!:1 {&a. each 256#.inv each a
> 672
>
>
> Leaving numbers in array form can also have some speed advantages in certain
> operations. Some math routines:
>
> coclass 'xint'
> square =: +//.@:(*/~)
> mult =: +//.@:(*/)
> join =: ,:&.|. NB. take multiple xints in reverse order so fills line up.
> used for addition/sub. xtoa9r better constructor
> multreduce =: [: +//. 1000000000&(<.@%~ ,. |) NB. use twice ^:2 for final
> answer. Once usually ok to prevent overflow
> m =: multreduce^:2@:mult
>
>
> a2 =. xtoa9r a NB. results: matrix of integers in array form. wrong endian.
>
> 10 timespacex '+/ a2'
> 1.344e_6 2304 NB. close to factor of 6
> 10 timespacex '+/ a'
> 7.328e_6 3328
>
>
> 10 timespacex '|. m_xint_&.|./ 7{. a2'
> 7.2448e_5 16640
> 10 timespacex '*/ 7{. a' NB. mult is a bit slower... but this is in J
> not C.
> 3.3344e_5 4352
>
>
> though faster boxed without fills
>
>
> a3 =. xtoa9 each a
> 10 timespacex 'm_xint_ each/ 7{. a3'
> 4.2528e_5 7680
>
>
>
> aa =. xtoa9 aar
>
>
> 10 timespacex 'm_xint_^:4~ aa'
> 4.4608e_5 13184 NB. exponentiation 5x faster
> 10 timespacex 'aar ^ 5'
> 0.000263232 12928
>
>
> Other ways to do small multiplication and division and convert to x:
>
> (2*aar) = 1000000000x p.~ 2 * |. aa
> (2%~aar) = 1000000000x p.~ 1r2 * |. aa
>
>
> It would be much appreciated if you can make or point me to fast modular
> exponentiation code... And other math functions. There is probably better
> multiplication algorithm too.
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
