Re: using smaller bases than possible so as to make use of the comba method?

On Oct 30, 4:26 am, Tom St Denis <t...@xxxxxxx> wrote:
On Oct 29, 10:48 pm, yawnmoth <terra1...@xxxxxxxxx> wrote:

According to section 5.2.2 of <http://math.libtomcrypt.com/files/
tommath.pdf>, the "defaults for LibTomMath are β (the radix) = 2**28
and  α (the maximum value) = 2**64".  On the surface, it seems like
2**32 would be a better choice but I'm wondering if that wasn't chosen
so that the comba technique could be used on more digits?  If the
radix were 32 bits then the comba technique could only be used on one
digit, per floor(2**64 / (2**(2*32) - 2**(33) + 1)) == 1, which would
seem to make it not all that useful.

It's a tradeoff made because LTM is 100% portable C.  So to do the
muladd in C you need to use fewer bits per digit.  In the case of 28
it means that your products are 8 bits shorter than a unsigned long
long, meaning you can have a column 256 deep for a max int size of
28*256=7168 with that routine, LTM can handle bigger as it will just
not use the comba routine on larger ints.

If I had chosen [say] 30-bits per digit, than I'd have 4 bits to spare
and can only handle numbers upto 16x30=480 bits with the comba, and
have to use the slower method for anything larger.  So while 28-bits
means more multiplications, it's faster [than 30-bits] because the
muladd step is more efficient.


I don't see muladd discussed in the pdf, but Java's BigInteger.java
implements it and, to be honest, I'm not really sure I see the
advantage of it there. From their multiply function:

private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen,
int[] z) {
int xstart = xlen - 1;
int ystart = ylen - 1;

if (z == null || z.length < (xlen+ ylen))
z = new int[xlen+ylen];

long carry = 0;
for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) {
long product = (y[j] & LONG_MASK) *
(x[xstart] & LONG_MASK) + carry;
z[k] = (int)product;
carry = product >>> 32;
}
z[xstart] = (int)carry;

for (int i = xstart-1; i >= 0; i--) {
carry = 0;
for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {
long product = (y[j] & LONG_MASK) *
(x[i] & LONG_MASK) +
(z[k] & LONG_MASK) + carry;
z[k] = (int)product;
carry = product >>> 32;
}
z[i] = (int)carry;
}
return z;
}

There are a total of three loops (two sets) - the second for loop has
another for loop inside it whereas the first one doesn't. The mulAdd
function is largely identical save for that the second set of for
loops isn't there - it's just the first one. In doing it that way,
they save themselves from having to add z[k] & LONG_MASK. Plus, if x
is just one digit long then xstart will be 0 and i, in the second for
loop, will start off at -1, which isn't >= 0, so the second for loop
will never be ran. Sure, maybe saving yourself from having to do an i
= 0 operation is worthwhile, but it doesn't seem like one trivial
operation like that is going to have much of an impact in the long run.
.

Relevant Pages

  • Re: using smaller bases than possible so as to make use of the comba method?
    ... radix were 32 bits then the comba technique could only be used on one ... meaning you can have a column 256 deep for a max int size of ... not use the comba routine on larger ints. ... If I had chosen 30-bits per digit, than I'd have 4 bits to spare ...
    (sci.crypt)
  • Re: What does this Code Actually do Please
    ... Dim LastDigit As Integer ... Dim nDupl As Integer ... ' Formula finds the last digit without needing to loop; ...
    (microsoft.public.excel.programming)
  • Re: Compression identical to its inverse?
    ... | the final bit-coding stage in a compression system). ... for the first locational digit. ... REM P = Starting Location Permutations, change this to change the shuffle ... REM IF-THEN loop checks if P>32 to do the lazy loop wraparound ...
    (comp.compression)
  • Re: Radix Sorting
    ... I'm trying to do the most basic of radix sorting and it was hard for me to understand that code. ... Read the first number from the list, and the appropriate digit from that number, and place the digit into the according bin. ... My program is one main recursive loop, ... All the recombine function does is take a two dimensional array of size 10 by whatever (linked lists) and append all the lists together into one. ...
    (comp.lang.c)
  • Re: VB slows down
    ... Even at 0 to 3 for each digit, ... odometer (even if each loop variable counts to different values) and translate ... keep a second array that holds the totals of the non changing digits. ... Dim idx As Long, j As Long ...
    (microsoft.public.vb.general.discussion)