• #### Expanding the basic types T and T2 to UINT32 and UINT64; Fast Modulus

Posted by Legacy on 03/18/2003 12:00am

Originally posted by: Anton

```1.) ---- UINT32 and UINT64 ----

I replaced
typedef USHORT T;
typedef ULONG LT;
with
typedef UINT32 T;
typedef UINT64 LT;
and got a performance improvement of about 20 percent with VC6

Unfortunately the division did not work.

I solved the problem by replacing the line
LT d = (1 << T_BIT)
with
LT d = (LT(1) << T_BIT)

2.) ---- Fast Modulus ----

I found a nice procedure to calculate
CLongInt<bits> % long
at http://www2.ics.hawaii.edu/~wes/ICS623/Arith.html

(UL means UINT32, a is Little Endian)

<Quote>
/* This function calculates a mod k where  */
/* a is a 512-bit (16 word) number and k   */
/* is less than 2^15.        WP--10/02     */

UL rr(UL *a, UL k)
{
int i;
UL m, ans;

m = ((0xffffffff % k) + 1) %k; /* 2^32 mod k */
ans = 0;
for(i = 15; i>=0; i--) {
ans = (ans*m) % k;
ans = (ans + a[i])%k;
}
return ans%k;
}
</Quote>

I would be happy if you translate this algorithm into your excellent work. If you do this, the audience will probably ask for corresponding optimizations for
CLongInt<bits> / long
CLongInt<bits> * long
CLongInt<bits> + long
CLongInt<bits> - long

Best regards
Anton

```

• #### Bug in ToString()?

Posted by Legacy on 03/15/2003 12:00am

Originally posted by: Pawel Guzowski

Why do I always get "0077042C" as the result when I do ToString(base), whatever the actual number, whatever the size, whatever the base? (maybe it's bug in my compiler, dont know, but using MSVC++).

Cheers.

• #### This a good work! But performance is very limit

Posted by Legacy on 01/15/2003 12:00am

Originally posted by: Solomon Wu

This a good work! But performance isn't very good.
For CLongInt<T> a , when T>1000000, performance speedy change to bad

• #### Excellent. "Scientific Expression"?

Posted by Legacy on 10/14/2002 12:00am

Originally posted by: X Tan

Thank you very much for your excellent work, Mr Thomas Holte.

If the numbers could automatically expressed as scientific expression (e.g. 4e-32, 1.35e40) when the numbers are too large to appear in the fix room, it will be perfect.

Could you please provide with some clues to do that, Thomas. Or anyone know how to do it?

• #### Beautiful

Posted by Legacy on 10/06/2002 12:00am

Originally posted by: Bappi

```Hi;
Its totally helpfull for every programmer.
I also include my website... for my friends.
Excellent work....I can call it ,"Our Bossom Friend".

Thanks for everything
Thanks again
Bappi

But if there some security program code then it will be more helpfull.
```

• #### Nice work!!

Posted by Legacy on 09/13/2002 12:00am

Originally posted by: Gilbert

Thank you very much.

It's so nice and useful thing.

• #### great work, thanks!

Posted by Legacy on 08/20/2002 12:00am

Originally posted by: Stefan Ganscha

as per subject

• #### Good work, but there's a better implementation.

Posted by Legacy on 03/21/2002 12:00am

Originally posted by: Gabriel Praino

Good code!!! but there's a problem with this implementation.

In many applications, it's very common to work with very different integer sizes.

A situation where long integers are very used are encryption algorithms. Allmost all public key algorithms used to sign and encrypt information all over the world are based on long integers, which may have 1024 or more bits.

In this kind of applications, it's very common to work with integer of 512, 768, 1024 and 2048 bits.
In some situations, you require even more bits to perform some kind of operations.

If you use the maximun bit size allways, you'll get a very poor performance (encryption requires extremely fast algorithms), but compiling the code with many different integer sizes would result in an inneficient code also. If we also consider converting from a bit size to another this would becomes a caos.

I once had to programm a class to do this, and I rather prefer to use a code which dinamically allocates memory and can handle any bit size.

Of course, allocating memory has a cost, but in many application this is preferred.

• #### Bug in function Divide. Here's the fix...

Posted by Legacy on 03/11/2002 12:00am

Originally posted by: Serge Debner

```Very nice class, but I found a bug in Divide function.
When working with very large numbers (I'm working with 1024 bit values)
the result of the Divide function is not always correct.
This happens due to the error in the implementation of Knuth's long division algorithm.
Here's the fix I've come up with.
Maybe someone can come up with the better one, but this seems to be working fine for me.
I've done a lot of testing.

Replace the following original code:

// Problem code starts
/*
for (;; q_hat--)
{
// The following statements build up... blah...blah...
// ...
union
{
LT L[2];
T  S[4];
} u_j_q_hat;

u_j_q_hat.L[0] = 0;
u_j_q_hat.S[2] = uv[j];
u_j_q_hat.S[3] = uv[j + 1];
// ... - vv[0] * q_hat
u_j_q_hat.L[1] -= vv[0] * q_hat;
if (u_j_q_hat.S[2] != 0)
break;

// ... * base
u_j_q_hat.S[2] = u_j_q_hat.S[3];
// ... + uv[j+2]
u_j_q_hat.S[2] = uv[j + 2];
if ((vv[1] * q_hat) <= u_j_q_hat.L[1])
break;
}
*/
// Problem code ends

with this code:

// New code starts
if (vv[1] * q_hat > (((((uv[j] << T_BIT) + uv[j + 1]) - vv[0] * q_hat) << T_BIT) + uv[j + 2]))
{
LT q_test = (static_cast < T>(~0));
if (q_hat != q_test && q_hat != 0)
q_hat--;
}
// New code ends

Hope this helps someone...

Serge

```

• #### Min and max

Posted by Legacy on 03/11/2002 12:00am

Originally posted by: Per Nilsson

```Nice article. Useful and clear.

I added Min and Max static methods that returns lowest
and highest possible values:
static CLongInt Max()
{

CLongInt w;
// Update this if the typedef T is changed
for (int i = 1; i < T_LEN; i++) w.m_data[i] = USHRT_MAX;
w.m_data[0] = USHRT_MAX/2;
return w;
}

static CLongInt Min()
{
return ~Max();
}

So, elsewhere in my code I can present the valid
range like:
CLongInt<256> l;
CString s;
s.Format("Valid range [%s,%s]",
l.Min().ToString(),
l.Max().ToString());

```