Originally posted by: Anton
1.) ---- UINT32 and UINT64 ----ReplyI replaced
typedef USHORT T;
typedef ULONG LT;
with
typedef UINT32 T;
typedef UINT64 LT;
and got a performance improvement of about 20 percent with VC6Unfortunately 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
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.
ReplyOriginally 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
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?
Originally posted by: Bappi
Hi;Reply
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
BappiBut if there some security program code then it will be more helpfull.
Originally posted by: Gilbert
Thank you very much.
It's so nice and useful thing.
Reply
Originally posted by: Stefan Ganscha
as per subject
Reply
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.
ReplyOriginally posted by: Serge Debner
Very nice class, but I found a bug in Divide function.Reply
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
Originally posted by: Per Nilsson
Nice article. Useful and clear.ReplyI 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());