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
