Factoring large numbers
Dann Corbit
"How fast does the product of all primes up to N grow in size"
for reference.
My proposed algorithm will give the GCD (which only needs modulus).
This GCD is very easy to factor, since it is much smaller than the
input number.
Also note that my algorithm is separable. What I mean is, let's
form some numbers called t, u, v, w, and x.
t = product for all primes from 1st to ith
u = product for all primes from (i+1)th to jth
v = product for all primes from (j+1)th tokth
w = product for all primes from (k+1)th tolth
x = product for all primes from (l+1)th to mth
if our huge input number is called q,
then if gcd(q,t) = 1
and gcd(q,u) = 1
and gcd(q,v) = 1
and gcd(q,w) = 1
and gcd(q,x) = 1
then gcd(q, t*u*v*w) = 1
further, q has no factors up to m squared.
If, on the other hand, any gcd's are revealed
then these are factors of q.
My algorithm will not reveal a lot about input numbers smaller
than m, other than primality. But with big inputs, each gcd
will be revealing.
I calculate that 4000 cd-roms could contain enough factors
to completely factor a 100 bit number. Further, with 4000
cpu's(each with its own cd reader) that 100 bit number could
be factored in the time it takes to read a single cd-rom. (which
is obviously the rate limiting step in this problem).
--
The opinions expressed in this message are my own personal views
and do not reflect the official views of Microsoft Corporation.
Dann Corbit
>
>In article <4gaeks$n...@news.microsoft.com>, a-c...@microsoft.com says...
>>I calculate that 4000 cd-roms could contain enough factors
>>to completely factor a 100 bit number. Further, with 4000
>>cpu's(each with its own cd reader) that 100 bit number could
>>be factored in the time it takes to read a single cd-rom. (which
>>is obviously the rate limiting step in this problem).
>>--
>We have to double the number of CD's for each two bits increase
>in size of our number to be factored.
>--
I don't know that this method will ever pass existing factoring
methods for efficiency. Given high enough density storage and
high enough storage accesss speed, it could become more generally
useful.
One possibly useful output from the techniqe described is the
method used for calculation of the modulus. Although it is not
a revolutionary or new notion, I have found that all of the extended
precision integer classes that I have examined ( though certainly
not comprehensive ) invariably do the actual division to calculate
the modulus. This makes GCD algorithms run orders of magnitude
slower than they need to. If they were to implement a simple ripple
modulus like that found in my code, the mod operation would be much
faster for these packages.
Dann Corbit
>I calculate that 4000 cd-roms could contain enough factors
>to completely factor a 100 bit number. Further, with 4000
>cpu's(each with its own cd reader) that 100 bit number could
>be factored in the time it takes to read a single cd-rom. (which
>is obviously the rate limiting step in this problem).
>--
About 17 minutes with current technology (6.7x cdroms).
We have to double the number of CD's for each two bits increase
in size of our number to be factored.
--
N.R.Bruin
>
> In article <4gaeks$n...@news.microsoft.com>, a-c...@microsoft.com says...
> >I calculate that 4000 cd-roms could contain enough factors
> >to completely factor a 100 bit number. Further, with 4000
> >cpu's(each with its own cd reader) that 100 bit number could
> >be factored in the time it takes to read a single cd-rom. (which
> >is obviously the rate limiting step in this problem).
> >--
> About 17 minutes with current technology (6.7x cdroms).
> We have to double the number of CD's for each two bits increase
> in size of our number to be factored.
Note that this is a VERY EXPENSIVE way of factoring such a number. A
100bit number is about 30 digits long. If it's not prime, there should
be a factor of at most 15 digits. These factors are easily found with
even a straightforward implementation of the elliptic curve method
(without 2nd step, that is) in less than an hour on a workstation.
Redo your calculation for 100 digit ( = about 300 bit) numbers. Then
we're getting in the range that's interesting nowadays. Quite a nice
illustration of why smart algorithms really pay off ...
Nils Bruin
Benjamin J. Tilly
a-c...@microsoft.com (Dann Corbit) writes:
> See the previous thread,
> "How fast does the product of all primes up to N grow in size"
> for reference.
>
> My proposed algorithm will give the GCD (which only needs modulus).
> This GCD is very easy to factor, since it is much smaller than the
> input number.
>
Not so fast. In order to find the GCD you have to DIVIDE the product by
your number. How long does this division take??? About the size of your
number!
> Also note that my algorithm is separable. What I mean is, let's
> form some numbers called t, u, v, w, and x.
> t = product for all primes from 1st to ith
> u = product for all primes from (i+1)th to jth
> v = product for all primes from (j+1)th tokth
> w = product for all primes from (k+1)th tolth
> x = product for all primes from (l+1)th to mth
>
> if our huge input number is called q,
> then if gcd(q,t) = 1
> and gcd(q,u) = 1
> and gcd(q,v) = 1
> and gcd(q,w) = 1
> and gcd(q,x) = 1
> then gcd(q, t*u*v*w) = 1
> further, q has no factors up to m squared.
> If, on the other hand, any gcd's are revealed
> then these are factors of q.
>
A marginal improvement. Now if it does not factor easily then it takes
multiple divisions. I am still not impressed by this as an idea. I
mean, this approach might be useful to deal with the first hundred or
so primes. However it scales VERY badly.
> My algorithm will not reveal a lot about input numbers smaller
> than m, other than primality. But with big inputs, each gcd
> will be revealing.
>
And will take correspondingly longer to calculate.
> I calculate that 4000 cd-roms could contain enough factors
> to completely factor a 100 bit number. Further, with 4000
> cpu's(each with its own cd reader) that 100 bit number could
> be factored in the time it takes to read a single cd-rom. (which
> is obviously the rate limiting step in this problem).
Actually not. Before you can GET the GCD you have to go through a good
chunk of the cd-roms. (If it has no small factors then you might have
to go through all of them.) What is wrong with this picture?
This is not to mention the "detail" of how inconvenient 4000 cd-roms of
memory is. (That is a lot of memory. How much does, say, UPS use?)
Standard factoring algorithms are FAR faster than this one would be.
And can handle *much* larger numbers with reasonable computing power.
Ben Tilly
(If Microsoft uses algorithms like this, that would explains some
things...)
numt...@tiac.net
>See the previous thread,
>"How fast does the product of all primes up to N grow in size"
>for reference.
I replied to this earlier, but the post did not seem to make it out to
the net.
The product of all primes less than N is asymptotically
exp(N + o(1))
>My proposed algorithm will give the GCD (which only needs modulus).
>This GCD is very easy to factor, since it is much smaller than the
>input number.
>I calculate that 4000 cd-roms could contain enough factors
>to completely factor a 100 bit number. Further, with 4000
Not even close. With N = 10^100 the product of the primes needed
is about e^(10^50). If one could store each bit (somehow)
in a space the size of the Planck length, there would not be
enough space in the entire universe to hold the number.
You can lead a horse's ass to knowledge, but you can't make him think.
Dann Corbit
The largest 100 bit number I know of is approximately 1.26765e30.
The square root of that number is about 1.1259e15. After all,
if any number has one or more factors, at least on is <= sqrt(x).
One CD can hold about 8 billion bits.
1.1259e15/8e9 = 1.6125e5
161,250 is a lot more than 4000, but it will fit in the known universe.
>You can lead a horse's ass to knowledge, but you can't make him think.
>
Neigh! Whinnie! Snort!
Dann Corbit
>
>In article <4gdvgq$c...@sundog.tiac.net>, numt...@tiac.net says...
>>
>>a-c...@microsoft.com (Dann Corbit) wrote:
>>
>>>See the previous thread,
>>>"How fast does the product of all primes up to N grow in size"
>>>for reference.
>>
>>I replied to this earlier, but the post did not seem to make it out to
>>the net.
>>
>>The product of all primes less than N is asymptotically
>>
>>exp(N + o(1))
>>
>>>My proposed algorithm will give the GCD (which only needs modulus).
>>>This GCD is very easy to factor, since it is much smaller than the
>>>input number.
>>
>>
>>>I calculate that 4000 cd-roms could contain enough factors
>>>to completely factor a 100 bit number. Further, with 4000
>>
>>Not even close. With N = 10^100 the product of the primes needed
>>is about e^(10^50). If one could store each bit (somehow)
>>in a space the size of the Planck length, there would not be
>>enough space in the entire universe to hold the number.
>
>The largest 100 bit number I know of is approximately 1.26765e30.
actually (2^101-1) is approximately 5.07e30,
the square root of which is about 2.2518e15
I was previously thinking of 2^100, which is the SMALLEST 100 bit
number, not the largest.
>The square root of that number is about 1.1259e15. After all,
>if any number has one or more factors, at least on is <= sqrt(x).
>One CD can hold about 8 billion bits.
>1.1259e15/8e9 = 1.6125e5
>
>161,250 is a lot more than 4000, but it will fit in the known universe.
Ok, 320K CD's But we may be able to compress the data, on the other hand.
Even this large number will fit into a single Galaxy (a Ford Galaxy 500).
>
>>You can lead a horse's ass to knowledge, but you can't make him think.
>Neigh! Whinnie! Snort!
This time I plead Donkey...
EeeAwwh! EeeAwwh! EeeAwwh!
Dann Corbit
>
>Note that this is a VERY EXPENSIVE way of factoring such a number. A
>100bit number is about 30 digits long. If it's not prime, there should
>be a factor of at most 15 digits. These factors are easily found with
>even a straightforward implementation of the elliptic curve method
>(without 2nd step, that is) in less than an hour on a workstation.
>
>Redo your calculation for 100 digit ( = about 300 bit) numbers. Then
>we're getting in the range that's interesting nowadays. Quite a nice
>illustration of why smart algorithms really pay off ...
>
this method as a good way to factor large numbers. It is interesting
(at least to me) as a theoretical approach that is easily understood.
Perhaps the basic concept can be put to good use on some other problem.
Or, someday, very high speed super dense memory access will be invented.
In such a case it could become more generally useful.
Benjamin J. Tilly
numt...@tiac.net writes:
> a-c...@microsoft.com (Dann Corbit) wrote:
>
> >See the previous thread,
> >"How fast does the product of all primes up to N grow in size"
> >for reference.
>
> I replied to this earlier, but the post did not seem to make it out to
> the net.
>
> The product of all primes less than N is asymptotically
>
> exp(N + o(1))
>
> >My proposed algorithm will give the GCD (which only needs modulus).
> >This GCD is very easy to factor, since it is much smaller than the
> >input number.
>
>
> >I calculate that 4000 cd-roms could contain enough factors
> >to completely factor a 100 bit number. Further, with 4000
>
> Not even close. With N = 10^100 the product of the primes needed
> is about e^(10^50). If one could store each bit (somehow)
> in a space the size of the Planck length, there would not be
> enough space in the entire universe to hold the number.
>
Sorry, but Dann is in the right general ballpark here..
100 *bits* is 30 digits. To factor it I just need the factors up to
10^15. Therefore I am dealing with a number of size e^(10^15), which
means that I need order of magnitude 10^15 digits. (Actually it is a
bit smaller than that.) With 4000 cd-roms that brings it down to
something on the order of 10^11 digits per cd-rom. I am not sure
whether or not this is doable on a good cd-rom or not, but it is not
too outrageous.
Of course for the reason that you are talking about it is impossible
for us to solve interesting problems using this method...
>
> You can lead a horse's ass to knowledge, but you can't make him think.
>
Ben Tilly
Dann Corbit
>Not so fast. In order to find the GCD you have to DIVIDE the product by
>your number. How long does this division take??? About the size of your
>number!
do you count?
/*******************************************************/
/* This function uses the Euclidean Algorithm to */
/* calculate the greatest common divisor of two long */
/* integers. */
/*******************************************************/
/* Programmer: Danniel R. Corbit */
/* */
/* Copyright (C) 1992 by Danniel R. Corbit */
/* All rights reserved. */
/*******************************************************/
/* Reference: "Factorization and Primality Testing", */
/* by David M. Bressoud, */
/* Springer-Verlag 1989. */
/* pages 7-12. */
/*******************************************************/
long gcd(long a, long b)
{
int shiftcount = 0;
long tmp;
/*******************************************************************/
/* This zero testing stuff may seem odd, since zero is not likely. */
/* However, knowing that neither a nor b is zero will speed up */
/* later operations greatly by elimination of tests for zero. */
/*******************************************************************/
if (a == 0L)
{
tmp = b;
}
else if (b == 0L)
{
tmp = a;
}
else /* Neither a NOR b is zero! */
{
/* Absolute values used. */
a = a > 0 ? a : -a;
b = b > 0 ? b : -b;
/**************************************************************/
/* While all this fuss about numbers divisible by 2 may seem */
/* like quite a bother, half of the integers in the universe */
/* are evenly divisible by 2. Hence, on a random sample of */
/* input values, great benefit will be realized. The odds */
/* that at least one of a,b is even is 1 - (1/2)*(1/2) = .75 */
/* since the probability that both are odd is .25. */
/**************************************************************/
/* If the last bit is 0, the number is divisible by 2 evenly. */
/* If a & b are divisible by 2, gcd(a,b) = 2*gcd(a/2,b/2). */
/**************************************************************/
while (!(a & 1L) && !(b & 1L))
{
a >>= 1;
b >>= 1;
shiftcount++;
}
/**************************************************************/
/* If the a is divisible by 2 and b is not divisible by 2, */
/* then gcd(a,b) = gcd(a/2,b). */
/**************************************************************/
while (!(a & 1L))
{
a >>= 1;
}
/*******************************************************/
/* If b is divisible by 2 and a is not divisible by 2, */
/* then gcd(a,b) = gcd(a,b/2). */
/*******************************************************/
while (!(b & 1L))
{
b >>= 1;
}
/**********************************************************************/
/* Make sure the numbers are in the proper order (swap if necessary). */
/**********************************************************************/
if (b > a)
{
tmp = a;
a = b;
b = tmp;
}
/****************************************/
/* Euclid's famous gcd algorithm: */
/* Iterate until the remainder is <= 1. */
/****************************************/
while (b > 1)
{
tmp = b;
b = a % b;
a = tmp;
}
if (b == 0)
tmp = a;
else
tmp = b;
/***********************************************************************/
/* If we divided BOTH numbers by factors of 2, we must compensate now. */
/***********************************************************************/
if (shiftcount > 0 && tmp > 0L)
tmp <<= shiftcount;
}
return (tmp);
}
>Standard factoring algorithms are FAR faster than this one would be.
>And can handle *much* larger numbers with reasonable computing power.
Absolutely agreed. There may be some smart folks out there that can
see some useful purpose for the math involved however, or it may be
useful for factoring in certain bands.
>Ben Tilly
>
>(If Microsoft uses algorithms like this, that would explains some
>things...)
It certainly would not explain how they became the most powerful and
influential software company in the world.
--
The opinions expressed in this message are my own personal views
and do not reflect the official views of Microsoft Corporation.
In fact, I'm just a subcontractor, not an employee, so pull in your claws.
Ian Gay
a-c...@microsoft.com (Dann Corbit) wrote:
>In article <4gdgpe$k...@dartvax.dartmouth.edu>, Benjamin...@dartmouth.edu
says...
>>Not so fast. In order to find the GCD you have to DIVIDE the product by
>>your number. How long does this division take??? About the size of your
>>number!
>Not the way I do it. Here's a C program that does GCD's on INT's. How many
divisions
>do you count?
Hmmm... how does your computer implement % :-)
David M Einstein
: In article <4gdgpe$k...@dartvax.dartmouth.edu>, Benjamin...@dartmouth.edu says...
: >Not so fast. In order to find the GCD you have to DIVIDE the product by
: >your number. How long does this division take??? About the size of your
: >number!
: Not the way I do it. Here's a C program that does GCD's on INT's. How many divisions
: do you count?
Yes, but this is after the first division. That first division
is going to take time proportional to the size (in bits) of your number.
: >Standard factoring algorithms are FAR faster than this one would be.
: >And can handle *much* larger numbers with reasonable computing power.
: Absolutely agreed. There may be some smart folks out there that can
: see some useful purpose for the math involved however, or it may be
: useful for factoring in certain bands.
Until it becomes faster than trial division, it is unlikely
to be useful as anything other than the answer to exercise 4.5.4.3.
: >Ben Tilly
: >
: >(If Microsoft uses algorithms like this, that would explains some
: >things...)
: It certainly would not explain how they became the most powerful and
: influential software company in the world.
Announcing something that is at best 25% slower, and measurably
less useful, than the slowest algorithm in use as an advance seems to
be precisely what makes Microsoft both extremely profitable and hideously
annoying. Though I thought that claiming that long division was orders
of magnitude faster than long division was a classic worthy of the master,
and much more Microsoftian.
: --
: The opinions expressed in this message are my own personal views
: and do not reflect the official views of Microsoft Corporation.
: In fact, I'm just a subcontractor, not an employee, so pull in your claws.
--
David M Einstein | Lord, grant me the companionship of those who seek | the truth, and protection from those who have found
Dik T. Winter
> In article <4gdgpe$k...@dartvax.dartmouth.edu>, Benjamin...@dartmouth.edu says...
> >Not so fast. In order to find the GCD you have to DIVIDE the product by
> >your number. How long does this division take??? About the size of your
> >number!
Ben, you ought to know better. But Dann's response is off-track too (he
just replaces division by taking the mod). See Knuth, Vol. 2, I think.
From the top of my head (and absolutely untested):
unsigned gcd(unsigned i, j)
{
unsigned tmp, i2 = 0, j2 = 0;
if(i == 1 || j == 1) return 1;
if(i != 0) while(!(i & 1)) { i >>= 1; i2++;}
if(j != 0) while(!(j & 1)) { j >>= 1; j2++;}
if(i > j) { tmp = i; i = j; j = tmp;}
while(i != 0) {
j -= i;
if(j != 0) while(!(j & 1)) j >>= 1;
if(i > j) { tmp = i; i = j; j = tmp;}
}
return j + 1 << (i2 < j2 ? i2 : j2);
}
See? No division, only by 2 (which is much faster than true division
on a binary machine, because it is a shift). Knuth discusses
the merits of both Euclids and this (binary) algorithm at length. Both
are similar in time complexity and worst case. Euclids is worst case if
the two numbers are succesive Fibonacci numbers; off-hand I do not know
the worst case for the binary algorithm, but it is similar.
{ From a purely mathematic viewpoint, there is of course no difference
between a division by 2 and a division by any other number. For a
computer scientists viewpoint there is a huge difference, unless he
is a Soviet computer scientist working with the, now defunct, base 3
computer (Setun).}
Still the question and the response are not in any way related to the
question whether the method is feasable or not. Doing a MOD (or GCD)
of a large product of primes and another (smaller) number is in time
complexity related to the size of the largest number (as Ben states and Dann
implicitly states when he is talking about time needed reading numbers).
> >Standard factoring algorithms are FAR faster than this one would be.
> >And can handle *much* larger numbers with reasonable computing power.
This one is absolutely true. Factoring a 60 digit (decimal digits that
is) will take only a few minutes on a reasonable workstation. Also
a Cray will factor a 20 digit number using trial division within
one hour. (And you may precompute the primes or not; it will not make
very much difference.) Using some standard methods will take you in
minutes, or even seconds.
>
> Absolutely agreed. There may be some smart folks out there that can
> see some useful purpose for the math involved however, or it may be
> useful for factoring in certain bands.
I do not think it is useful whatever. Not even in primality testing
(which is all Dann's algorithm really does). And for Dann, the program
I have to test primality is by Cohen and Lenstra; there is a short
description on it in some back number of Mathematics of Computation. I
think the 1981-1983 period.
...
> >(If Microsoft uses algorithms like this, that would explains some
> >things...)
I think, Ben, that this is uncalled for. Posting from microsoft in no
way should involve microsoft in the postings (as my posting this from
cwi should in no way involve cwi in the contents).
> It certainly would not explain how they became the most powerful and
> influential software company in the world.
On the other hand, Dann, being the most powerful and influential does
not make it necessarily the best.
Can we dispose off affiliations?
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Roy Lakin
}In article <4gl686$2...@news.microsoft.com>,
} a-c...@microsoft.com (Dann Corbit) wrote:
}says...
}>>Not so fast. In order to find the GCD you have to DIVIDE the product by
}>>your number. How long does this division take??? About the size of your
}>>number!
}>Not the way I do it. Here's a C program that does GCD's on INT's. How many
}divisions
}>do you count?
}
Repeated subtraction :-)
roy
Dann Corbit
>
>Dann Corbit (a-c...@microsoft.com) wrote:
>: In article <4gdgpe$k...@dartvax.dartmouth.edu>, Benjamin...@dartmouth.edu says...
>: >Not so fast. In order to find the GCD you have to DIVIDE the product by
>: >your number. How long does this division take??? About the size of your
>: >number!
>: Not the way I do it. Here's a C program that does GCD's on INT's. How many divisions
>: do you count?
/********************************************************************/
/* This is a base 10 array of the product of all primes up to 65535 */
/* It would be much nicer if it were binary and hexadecimal. */
/********************************************************************/
static unsigned long gulPop[3145] =
{
664294312UL, 873588591UL, 557696282UL, 245080384UL, 613808600UL,
692072289UL, 299106734UL, 227519427UL, 216562269UL, 334647365UL,
766239130UL, 550478814UL, 511606893UL, 741397102UL, 226899229UL,
592648042UL, 29334009UL, 556195606UL, 460038548UL, 885243012UL,
915724086UL, 88933150UL, 947844648UL, 962127227UL, 57503685UL,
79074520UL, 504204641UL, 963637568UL, 361509564UL, 712554731UL,
536709093UL, 444200873UL, 839578014UL, 224997581UL, 169606987UL,
447005891UL, 344530361UL, 460695481UL, 120350492UL, 676281066UL,
779643313UL, 109845937UL, 291835830UL, 591238181UL, 827151151UL,
9778678UL, 653674198UL, 23449317UL, 675178043UL, 403160690UL,
141565712UL, 372806288UL, 424521963UL, 746776431UL, 503438964UL,
269820990UL, 956342782UL, 943941245UL, 756580810UL, 70290909UL,
721207921UL, 954876543UL, 302091151UL, 500005637UL, 335463840UL,
825814644UL, 905229649UL, 471756751UL, 774157609UL, 378642831UL,
29380081UL, 200989980UL, 353728995UL, 541571528UL, 925052067UL,
362528008UL, 67901786UL, 17910320UL, 792470370UL, 151712638UL,
151335422UL, 778326714UL, 762560890UL, 693857620UL, 24107975UL,
928964781UL, 885832717UL, 455143331UL, 405615508UL, 597701432UL,
765328412UL, 505887470UL, 69746527UL, 21920202UL, 101980042UL,
621921604UL, 651206895UL, 349245634UL, 289423213UL, 589870994UL,
260996904UL, 587945567UL, 230817159UL, 685332345UL, 157307873UL,
149533560UL, 650747529UL, 443816913UL, 977810088UL, 613335551UL,
696421967UL, 60900485UL, 74173948UL, 223212787UL, 591719152UL,
643895516UL, 542754302UL, 832861025UL, 566397679UL, 248767980UL,
266219420UL, 88389364UL, 921524056UL, 865561832UL, 550898752UL,
972463827UL, 420254261UL, 530230107UL, 15695110UL, 85159942UL,
966938284UL, 125453441UL, 755512045UL, 631601058UL, 463705839UL,
402331786UL, 978011511UL, 368593018UL, 893495969UL, 673193789UL,
487884349UL, 43804363UL, 893603032UL, 439809879UL, 528794823UL,
699444136UL, 334925932UL, 775766686UL, 462902840UL, 219206553UL,
505420500UL, 787934642UL, 762298323UL, 250592086UL, 676640222UL,
475394674UL, 271267116UL, 860123143UL, 569636394UL, 655071922UL,
810862471UL, 281342670UL, 274405520UL, 839394000UL, 581029373UL,
614876384UL, 970097679UL, 583676205UL, 241282770UL, 396713388UL,
372294002UL, 336419808UL, 334454967UL, 731304490UL, 47458465UL,
850619525UL, 334828990UL, 220030656UL, 514586982UL, 922714610UL,
380252772UL, 562653135UL, 748569019UL, 447122144UL, 172164961UL,
237868814UL, 662061782UL, 747322200UL, 821818832UL, 983236531UL,
382728161UL, 662178309UL, 119563343UL, 907186381UL, 636138067UL,
332727535UL, 940784UL, 288177101UL, 379969575UL, 459314289UL,
879627738UL, 887094933UL, 551102262UL, 431855758UL, 698190052UL,
637562011UL, 986602071UL, 795574857UL, 43303039UL, 12474926UL,
807434439UL, 622321558UL, 963528649UL, 34285925UL, 435997441UL,
831708915UL, 415773485UL, 726592216UL, 610202570UL, 714152758UL,
526418056UL, 16320210UL, 52924093UL, 410212199UL, 195453446UL,
505961754UL, 151852060UL, 11774457UL, 149961236UL, 225092743UL,
843593049UL, 944390631UL, 939484170UL, 18037044UL, 109733742UL,
758364190UL, 603936125UL, 976650870UL, 671196062UL, 166809111UL,
303562926UL, 769367041UL, 542166826UL, 254045509UL, 351778984UL,
612311316UL, 113036931UL, 134710079UL, 520197202UL, 939872029UL,
521910739UL, 793914535UL, 494900852UL, 576235513UL, 115535205UL,
380678254UL, 679480307UL, 251516766UL, 15561622UL, 253162370UL,
971111707UL, 774400393UL, 555728035UL, 248327261UL, 471675598UL,
308082375UL, 85566624UL, 652206859UL, 385659162UL, 599560708UL,
706589313UL, 218953035UL, 895648881UL, 232468167UL, 835282942UL,
812310109UL, 644190932UL, 631317216UL, 459772285UL, 12553786UL,
651505120UL, 584093823UL, 556467259UL, 89406884UL, 580804215UL,
987672169UL, 800883405UL, 635229136UL, 692628023UL, 346037432UL,
853813750UL, 699205036UL, 645927199UL, 680972899UL, 730049233UL,
786061510UL, 506991051UL, 767522945UL, 656882092UL, 48610690UL,
370686018UL, 161946135UL, 554340718UL, 155042881UL, 568841237UL,
660787454UL, 623322527UL, 657649459UL, 803574801UL, 185536290UL,
290335300UL, 349119994UL, 684824732UL, 883661000UL, 279969799UL,
448344906UL, 653948043UL, 799692165UL, 755551821UL, 190733925UL,
750529611UL, 505079781UL, 810225445UL, 140081734UL, 860862607UL,
451848855UL, 201041443UL, 235296598UL, 763449654UL, 724274807UL,
790092660UL, 859848753UL, 247911152UL, 279717109UL, 87244465UL,
315454843UL, 71252834UL, 684645507UL, 160978263UL, 85650060UL,
942260143UL, 649007252UL, 87087535UL, 805128978UL, 768646330UL,
786459536UL, 763690151UL, 459924294UL, 540940629UL, 804851648UL,
609224178UL, 40344534UL, 198618935UL, 247234971UL, 3399865UL,
635966830UL, 179984624UL, 511507000UL, 141511833UL, 561347083UL,
906383130UL, 270583249UL, 191676236UL, 594179003UL, 54046521UL,
411052858UL, 474915669UL, 400849346UL, 802108310UL, 685936670UL,
799144910UL, 681949029UL, 403544827UL, 528870351UL, 225084740UL,
137353440UL, 618102775UL, 874749079UL, 664878862UL, 337856067UL,
677303616UL, 881465358UL, 178344303UL, 826220727UL, 210018063UL,
619605120UL, 248022656UL, 291747612UL, 76001179UL, 773701499UL,
464124912UL, 398569284UL, 842596735UL, 444087685UL, 676543348UL,
180766411UL, 961621913UL, 21801290UL, 613547627UL, 50675798UL,
613875721UL, 520337314UL, 378232164UL, 888855603UL, 985152156UL,
633162995UL, 365492424UL, 343525505UL, 160584545UL, 850917066UL,
555725654UL, 187891394UL, 643557248UL, 934242125UL, 562341297UL,
812500258UL, 976625107UL, 570954003UL, 5078964UL, 710094221UL,
537596675UL, 582449215UL, 422350113UL, 33673032UL, 302021449UL,
178312454UL, 146636551UL, 468488089UL, 554448846UL, 20015229UL,
659659125UL, 12535031UL, 334823696UL, 801414530UL, 680581877UL,
31292162UL, 21717624UL, 813609083UL, 857726832UL, 665379804UL,
87697211UL, 736196728UL, 82798252UL, 877268606UL, 854398792UL,
14447627UL, 818256914UL, 135435080UL, 802869147UL, 937186498UL,
936605413UL, 587665437UL, 694206319UL, 708734860UL, 840102992UL,
161368005UL, 469878139UL, 970614695UL, 966448362UL, 643459139UL,
734741026UL, 870821379UL, 333637514UL, 741873508UL, 643268526UL,
549390230UL, 49621554UL, 284739523UL, 981559565UL, 888380088UL,
714171424UL, 70743935UL, 802934425UL, 784977050UL, 871138890UL,
82606778UL, 867856831UL, 184727627UL, 483718457UL, 828475588UL,
931039581UL, 72518760UL, 26638403UL, 474684267UL, 559589790UL,
677695223UL, 639464661UL, 138392586UL, 948618466UL, 33541277UL,
993994432UL, 170170732UL, 988676147UL, 989110855UL, 243778319UL,
793544063UL, 46443934UL, 398759300UL, 64382143UL, 503056023UL,
724594670UL, 575516914UL, 848065409UL, 579027286UL, 596438917UL,
806270299UL, 22787187UL, 631671330UL, 373195967UL, 229372020UL,
388375954UL, 736032894UL, 605418643UL, 681648233UL, 666465483UL,
900022587UL, 964685549UL, 626653085UL, 121649784UL, 269215722UL,
370363539UL, 265551701UL, 815949145UL, 100808081UL, 546739371UL,
33735231UL, 679425973UL, 84198405UL, 370140757UL, 474797405UL,
568728635UL, 390261000UL, 361420285UL, 506786559UL, 745895776UL,
289537128UL, 532036568UL, 297140921UL, 356493641UL, 214832054UL,
120858789UL, 188923597UL, 402396811UL, 491641859UL, 42452190UL,
516144025UL, 67157829UL, 889027899UL, 893806212UL, 446820586UL,
432611396UL, 134741679UL, 937867280UL, 73191979UL, 37922395UL,
607960573UL, 228550985UL, 455116161UL, 949034680UL, 686656276UL,
778698036UL, 650418980UL, 675523924UL, 458963526UL, 663373961UL,
188436818UL, 78730574UL, 993091503UL, 591378733UL, 453477091UL,
927566930UL, 903605515UL, 852348892UL, 894322368UL, 244785224UL,
640325702UL, 228728298UL, 769204460UL, 646306299UL, 360773679UL,
636760190UL, 255412883UL, 113708371UL, 922916075UL, 381269175UL,
130281806UL, 558014693UL, 121129368UL, 998826062UL, 105026840UL,
194294760UL, 670145052UL, 955003567UL, 579381592UL, 325678974UL,
210003310UL, 584510905UL, 499233233UL, 948199003UL, 994485352UL,
256729755UL, 236197523UL, 149427182UL, 288506751UL, 320539420UL,
561438855UL, 892397327UL, 899026880UL, 420346504UL, 889193917UL,
381376567UL, 663219965UL, 664987034UL, 302057619UL, 727078592UL,
452800522UL, 469288645UL, 711228947UL, 391323760UL, 436210555UL,
285175203UL, 710334154UL, 439166491UL, 832955761UL, 218738128UL,
987172013UL, 543245811UL, 842830794UL, 301151294UL, 365193163UL,
883205838UL, 246123151UL, 349183299UL, 505510897UL, 780294653UL,
923300487UL, 243920029UL, 283388793UL, 566973043UL, 681803684UL,
534421564UL, 433320478UL, 122124334UL, 210776731UL, 222840772UL,
956021054UL, 992644215UL, 340909109UL, 144930588UL, 768397379UL,
79944174UL, 218807676UL, 647661195UL, 559728867UL, 82913826UL,
93201306UL, 627807196UL, 372037814UL, 388090767UL, 237608805UL,
211423900UL, 490148103UL, 660683504UL, 725434949UL, 294804621UL,
65002411UL, 351123155UL, 188941519UL, 337946271UL, 565900759UL,
148269714UL, 70479931UL, 958007654UL, 875996200UL, 18333522UL,
412285609UL, 348600015UL, 658908568UL, 659639651UL, 605797093UL,
913094648UL, 95300006UL, 128032468UL, 823394700UL, 675866488UL,
446601764UL, 198998854UL, 941135906UL, 257600829UL, 31038817UL,
543423714UL, 12512387UL, 403134706UL, 445546599UL, 831907947UL,
848366925UL, 768881462UL, 793505714UL, 533465140UL, 85934287UL,
153817556UL, 972979012UL, 209541725UL, 386679679UL, 467534705UL,
238992617UL, 741786573UL, 451729715UL, 208512631UL, 141479638UL,
929152245UL, 134088610UL, 842129790UL, 690654777UL, 954254122UL,
968888044UL, 232433720UL, 820658645UL, 354913014UL, 67750663UL,
734578940UL, 389806908UL, 422789535UL, 863232112UL, 670302448UL,
227390374UL, 402541792UL, 436564002UL, 238049353UL, 781067735UL,
822721158UL, 257465370UL, 774093857UL, 129867913UL, 194888402UL,
480862529UL, 300116346UL, 326410873UL, 844494013UL, 125126028UL,
948887986UL, 812840925UL, 223918190UL, 431729765UL, 779981807UL,
516721218UL, 568325029UL, 274537225UL, 593365818UL, 431346356UL,
57605076UL, 348161317UL, 939641503UL, 820032479UL, 488678594UL,
116830114UL, 490937289UL, 321850267UL, 635594909UL, 298973549UL,
485892248UL, 884363252UL, 688981942UL, 378249850UL, 615745100UL,
62739331UL, 823399505UL, 125561578UL, 978028790UL, 597055446UL,
302357223UL, 884855262UL, 903092671UL, 803265041UL, 917435810UL,
797263160UL, 910523930UL, 611419590UL, 805856593UL, 501445058UL,
735203411UL, 287873518UL, 993304245UL, 936542118UL, 427628253UL,
484903531UL, 193177858UL, 967194655UL, 806557220UL, 517994525UL,
313017105UL, 242577695UL, 85899625UL, 593401121UL, 802544864UL,
421349380UL, 744052181UL, 27372406UL, 762526619UL, 232100168UL,
105610989UL, 758220268UL, 58576179UL, 265165669UL, 820366077UL,
906223425UL, 710890636UL, 377053362UL, 518664338UL, 478118860UL,
672730612UL, 991089013UL, 70390021UL, 262202769UL, 850561419UL,
150147818UL, 875557439UL, 272306377UL, 254706632UL, 49908724UL,
234682311UL, 229113789UL, 588524990UL, 286021956UL, 586530108UL,
801610654UL, 838309179UL, 432857985UL, 106433451UL, 343452718UL,
852493538UL, 324132638UL, 385035502UL, 401433757UL, 119057736UL,
617171252UL, 268728111UL, 662190151UL, 374012450UL, 518240779UL,
320639540UL, 825441090UL, 52832893UL, 890190715UL, 149097198UL,
92137999UL, 376656457UL, 355224070UL, 54413858UL, 765323481UL,
639607028UL, 873585328UL, 145422239UL, 507781614UL, 599526008UL,
62691652UL, 972424396UL, 427635447UL, 38371025UL, 303941403UL,
687153868UL, 443183378UL, 672823746UL, 358960756UL, 341503989UL,
381911488UL, 566401530UL, 543016852UL, 425348053UL, 40323206UL,
825891705UL, 250310230UL, 733979394UL, 773130617UL, 599940829UL,
698719033UL, 44130037UL, 195840838UL, 527365298UL, 185064654UL,
627611230UL, 844705984UL, 829801978UL, 439390355UL, 396839809UL,
435534339UL, 62888679UL, 415545906UL, 606734022UL, 383195356UL,
775142962UL, 315065299UL, 947625932UL, 191670241UL, 413973273UL,
164008610UL, 600201045UL, 749664824UL, 990651907UL, 553907130UL,
570096006UL, 437716626UL, 401356036UL, 795375061UL, 828368148UL,
611973619UL, 946813391UL, 106730324UL, 377245440UL, 73013588UL,
311671023UL, 329922649UL, 590361780UL, 844791839UL, 538152072UL,
200774760UL, 656738252UL, 907981914UL, 652085993UL, 357640400UL,
728582850UL, 32282137UL, 963570971UL, 127997236UL, 386394063UL,
385938599UL, 603501616UL, 725677991UL, 70724098UL, 16897878UL,
576292527UL, 570479766UL, 742488860UL, 531961680UL, 268175142UL,
248696205UL, 24928006UL, 369016953UL, 979975574UL, 446086984UL,
288304815UL, 564993718UL, 422132801UL, 681662848UL, 757216138UL,
370352100UL, 546467265UL, 894499599UL, 810777023UL, 40106090UL,
956939360UL, 205102341UL, 837125808UL, 216363561UL, 496302579UL,
47467115UL, 433312193UL, 526032433UL, 473049227UL, 686454052UL,
899784685UL, 239549459UL, 570017109UL, 132339647UL, 505630252UL,
362256416UL, 268562776UL, 960966450UL, 788733643UL, 952160049UL,
874388557UL, 364228396UL, 316703153UL, 356302775UL, 556574717UL,
685954912UL, 494186960UL, 687301295UL, 955349564UL, 465936672UL,
972517353UL, 238273843UL, 350246935UL, 627982005UL, 490928983UL,
22112191UL, 286677442UL, 471971688UL, 459800808UL, 151640700UL,
382974940UL, 735281498UL, 538957941UL, 406064086UL, 758211792UL,
446973227UL, 12359006UL, 757619811UL, 249325043UL, 520756958UL,
160881744UL, 407644537UL, 687773305UL, 522453464UL, 648546246UL,
980839120UL, 932961906UL, 479810579UL, 992604003UL, 925182955UL,
177568142UL, 728637678UL, 201254336UL, 636775482UL, 618247836UL,
12067003UL, 718320906UL, 308518776UL, 846710376UL, 691736975UL,
906480061UL, 966960671UL, 465939511UL, 304918060UL, 667470883UL,
759335227UL, 645064190UL, 635181955UL, 846702450UL, 508710696UL,
313254040UL, 397931131UL, 910367224UL, 897483800UL, 20814667UL,
811832142UL, 807079496UL, 752690554UL, 517760104UL, 731964827UL,
978955929UL, 796545291UL, 174876759UL, 541236874UL, 829668692UL,
373746382UL, 544570559UL, 877377178UL, 222695746UL, 537012557UL,
434295976UL, 25096224UL, 840421015UL, 707597083UL, 477571943UL,
727697908UL, 413919493UL, 466630363UL, 138008172UL, 775057475UL,
724937161UL, 399489679UL, 718879207UL, 853769830UL, 602575187UL,
380867963UL, 64017752UL, 875956359UL, 919372612UL, 254865068UL,
251997369UL, 802167164UL, 727494739UL, 196637440UL, 380136083UL,
213759959UL, 756168506UL, 524448697UL, 856931861UL, 823426899UL,
375561340UL, 594250311UL, 117175626UL, 560502212UL, 975134218UL,
933371507UL, 185012057UL, 908678174UL, 740829527UL, 231718849UL,
182171212UL, 618185902UL, 701976255UL, 473639682UL, 682193866UL,
390204112UL, 318653159UL, 881206635UL, 80273849UL, 87204037UL,
452070356UL, 151568836UL, 266699256UL, 547072235UL, 405318412UL,
29000212UL, 971842988UL, 963323619UL, 209197928UL, 129798560UL,
238311845UL, 474478123UL, 752566394UL, 637764640UL, 111276394UL,
364066008UL, 328278034UL, 434436088UL, 823487201UL, 656220824UL,
441942716UL, 398777083UL, 395651720UL, 337955421UL, 125505974UL,
290550781UL, 144256189UL, 716188419UL, 605113266UL, 908611999UL,
363700391UL, 165353395UL, 544956313UL, 967092633UL, 332576920UL,
676837635UL, 323665383UL, 259569657UL, 108760693UL, 383051358UL,
661804267UL, 812089074UL, 212255182UL, 455950995UL, 724641046UL,
445251906UL, 472130970UL, 634835513UL, 585028345UL, 196999885UL,
899919623UL, 620068306UL, 804954147UL, 643931128UL, 121285499UL,
31044222UL, 614000018UL, 122280740UL, 206190739UL, 971318469UL,
248294888UL, 175062562UL, 597847733UL, 572308365UL, 883295089UL,
95958392UL, 992159624UL, 821271605UL, 94659589UL, 964144682UL,
562256655UL, 815280678UL, 194123111UL, 3153540UL, 35406422UL,
184474948UL, 64807116UL, 583793041UL, 955537592UL, 653053170UL,
579409020UL, 463025652UL, 507167816UL, 738078533UL, 166436925UL,
24281323UL, 204920762UL, 811258998UL, 126295848UL, 640176845UL,
220369880UL, 460982009UL, 612718757UL, 26949261UL, 762735396UL,
132238459UL, 476656569UL, 359440096UL, 479979319UL, 322665461UL,
398177084UL, 961810056UL, 266497330UL, 37083924UL, 122483181UL,
203844731UL, 969755963UL, 746516469UL, 275741310UL, 134139339UL,
764967899UL, 492852240UL, 394394992UL, 11589632UL, 377807369UL,
658499359UL, 12554914UL, 152049352UL, 562982594UL, 923062856UL,
64938413UL, 304845515UL, 399900840UL, 953277276UL, 484100294UL,
808921572UL, 202603877UL, 97054867UL, 593433006UL, 299527912UL,
532255884UL, 422367391UL, 569631183UL, 657004659UL, 476684415UL,
89230796UL, 724891809UL, 50019877UL, 380402159UL, 419292222UL,
556285656UL, 740801284UL, 217624086UL, 521804846UL, 51410358UL,
789571108UL, 307489630UL, 840734317UL, 492313012UL, 276550156UL,
536374147UL, 8229496UL, 488943022UL, 777110008UL, 717032917UL,
784298160UL, 861420429UL, 323145783UL, 350435922UL, 349649219UL,
923929639UL, 645588712UL, 872910758UL, 148909370UL, 758763355UL,
492357839UL, 767241570UL, 538349012UL, 881803617UL, 609322740UL,
176309640UL, 673906292UL, 805569650UL, 24237925UL, 375410655UL,
273386981UL, 919796042UL, 253807962UL, 335170UL, 723082618UL,
116859018UL, 841006994UL, 771021638UL, 707207416UL, 591125897UL,
439672948UL, 846025568UL, 807277346UL, 80919077UL, 218889565UL,
195094251UL, 76769625UL, 260279843UL, 666975558UL, 127182175UL,
512308565UL, 153713735UL, 868022914UL, 164138027UL, 926571544UL,
697555872UL, 55566223UL, 771183570UL, 164360969UL, 474356239UL,
979610632UL, 184781699UL, 843195723UL, 155057490UL, 392875676UL,
408811265UL, 880366026UL, 870389479UL, 882823026UL, 685587633UL,
995439044UL, 451828461UL, 599691342UL, 523914140UL, 658642201UL,
65238808UL, 161895388UL, 927197540UL, 274286290UL, 388441079UL,
773795713UL, 914129856UL, 97046647UL, 308979089UL, 500288248UL,
52552045UL, 176373625UL, 547820513UL, 368519704UL, 923321523UL,
336419483UL, 713007182UL, 303983629UL, 846421083UL, 985981983UL,
227874765UL, 938761084UL, 75023053UL, 552025104UL, 561453924UL,
332532802UL, 703950678UL, 448532590UL, 341265489UL, 638501844UL,
7757673UL, 237845545UL, 704058388UL, 944360199UL, 567992046UL,
152816423UL, 349292094UL, 460610817UL, 604849154UL, 339971661UL,
416429077UL, 621226997UL, 140385778UL, 241117584UL, 159017223UL,
716027629UL, 919384543UL, 141572776UL, 445743216UL, 566854828UL,
289329033UL, 505560704UL, 305809845UL, 117522359UL, 41619010UL,
694205202UL, 180274672UL, 425551157UL, 234916189UL, 120590335UL,
438592695UL, 348077206UL, 747901566UL, 332615514UL, 571246887UL,
538494039UL, 864626435UL, 879092689UL, 308240216UL, 450285320UL,
916861702UL, 211775231UL, 150910442UL, 741501764UL, 746591583UL,
679757851UL, 883395300UL, 274025895UL, 76029431UL, 785490680UL,
853572349UL, 427606082UL, 135723506UL, 556576242UL, 185289628UL,
445913508UL, 234483729UL, 133702949UL, 926376828UL, 556914112UL,
996554071UL, 919731333UL, 168244406UL, 411137172UL, 502584078UL,
60715416UL, 89419374UL, 874246595UL, 508917143UL, 139424102UL,
6079437UL, 352771564UL, 871980461UL, 5593179UL, 976712782UL,
681308108UL, 983803462UL, 650155524UL, 290998349UL, 66707151UL,
609480422UL, 663558526UL, 137222489UL, 860962404UL, 543023729UL,
71936057UL, 752156724UL, 539796643UL, 214283350UL, 28104748UL,
649293132UL, 524177358UL, 848808898UL, 679761408UL, 581795279UL,
986248704UL, 368996755UL, 383335042UL, 815190444UL, 801149798UL,
994399173UL, 844251337UL, 176165373UL, 294730089UL, 311563101UL,
921387245UL, 553706272UL, 562871972UL, 101631505UL, 626029531UL,
281265636UL, 898327687UL, 654386641UL, 347934541UL, 600716235UL,
239424321UL, 567282095UL, 337213388UL, 154668179UL, 649042671UL,
282149452UL, 250178302UL, 556713617UL, 925149076UL, 157975608UL,
660104117UL, 497745478UL, 630746137UL, 768983792UL, 767227610UL,
123340230UL, 249642942UL, 271500949UL, 482005048UL, 251629220UL,
368713601UL, 598889009UL, 855251373UL, 93262853UL, 121661619UL,
293476871UL, 970423827UL, 248378838UL, 575196071UL, 570875266UL,
928109921UL, 767411279UL, 18971250UL, 869273246UL, 141591024UL,
126216603UL, 928846308UL, 588171404UL, 54622518UL, 963489795UL,
339749330UL, 145860013UL, 482630173UL, 111793324UL, 970751164UL,
162339998UL, 279168331UL, 981139778UL, 275816134UL, 2066946UL,
775714182UL, 441854594UL, 574833720UL, 88569567UL, 271220970UL,
894254058UL, 39629170UL, 442303427UL, 140210505UL, 880769660UL,
246489772UL, 27705923UL, 640689863UL, 592829268UL, 57307062UL,
748988009UL, 213839652UL, 198308587UL, 672018242UL, 192687577UL,
958377014UL, 493721281UL, 789118537UL, 938059332UL, 982468051UL,
363814271UL, 219580965UL, 715701225UL, 840205892UL, 56663649UL,
186647570UL, 686011248UL, 969692754UL, 665893127UL, 52481120UL,
105490224UL, 843340832UL, 693462622UL, 486381657UL, 950827408UL,
457119726UL, 738933004UL, 938619930UL, 986459902UL, 82414825UL,
300423434UL, 452294034UL, 701292409UL, 389849313UL, 136551114UL,
787397453UL, 34123804UL, 27309700UL, 966747275UL, 34402594UL,
145097426UL, 437310406UL, 303543309UL, 486196103UL, 112312482UL,
689999344UL, 927079260UL, 295916440UL, 910894287UL, 61992498UL,
221832981UL, 765439717UL, 537537418UL, 404517085UL, 348313098UL,
506258603UL, 675113197UL, 703630992UL, 548192332UL, 222355605UL,
379985700UL, 145191410UL, 695566570UL, 970861684UL, 120434424UL,
763472833UL, 5541417UL, 496986936UL, 349014284UL, 155952122UL,
808191084UL, 477807901UL, 897093UL, 914585153UL, 994748310UL,
344054629UL, 200843565UL, 235486056UL, 185181291UL, 807447602UL,
370696283UL, 559757973UL, 955819818UL, 36960076UL, 87708973UL,
898147501UL, 44257245UL, 737748617UL, 50536834UL, 808249122UL,
396008226UL, 451682633UL, 567515969UL, 322854229UL, 341898331UL,
649905487UL, 297845022UL, 267995548UL, 639359857UL, 252212418UL,
150217916UL, 575283369UL, 73620651UL, 286212620UL, 770099737UL,
873000131UL, 776038152UL, 474387216UL, 827946498UL, 926630138UL,
184828398UL, 105537722UL, 704285720UL, 668779573UL, 105520116UL,
548900190UL, 128938943UL, 156929289UL, 691666932UL, 9383443UL,
424611137UL, 920502288UL, 688536902UL, 203729265UL, 89728473UL,
270467826UL, 147818908UL, 192302919UL, 315430743UL, 204863660UL,
113035983UL, 622209876UL, 287271712UL, 663730728UL, 93828384UL,
684924643UL, 972441681UL, 563387743UL, 93160076UL, 500750426UL,
203874717UL, 594917709UL, 288467672UL, 91410632UL, 453770876UL,
886692447UL, 916546224UL, 556401979UL, 112191017UL, 816214307UL,
476267241UL, 688635504UL, 982225897UL, 351604727UL, 151462072UL,
597001238UL, 750487503UL, 189924018UL, 46780899UL, 353822522UL,
872934837UL, 906965577UL, 811804238UL, 997040803UL, 639156716UL,
899576856UL, 340610307UL, 940672647UL, 612659108UL, 84730908UL,
966769605UL, 220054404UL, 681682073UL, 91901366UL, 33583452UL,
314288918UL, 552747005UL, 605069854UL, 632911992UL, 69010705UL,
941095827UL, 991410047UL, 765317599UL, 793911921UL, 410118507UL,
984027993UL, 252709742UL, 864924546UL, 570324637UL, 485135449UL,
85648792UL, 908915050UL, 548752660UL, 214939831UL, 176602163UL,
460379590UL, 26069682UL, 508553343UL, 367472245UL, 7888181UL,
689705859UL, 201059112UL, 622196881UL, 749373229UL, 231178423UL,
273522109UL, 670408671UL, 385689377UL, 905307618UL, 398334393UL,
54722637UL, 717905954UL, 572252180UL, 24792826UL, 969123413UL,
997463630UL, 852421412UL, 771735202UL, 235625734UL, 56465592UL,
392253174UL, 69423938UL, 57505538UL, 585148455UL, 550463223UL,
934607157UL, 195385216UL, 180116709UL, 867998248UL, 114821503UL,
868617751UL, 717236328UL, 325851468UL, 490663864UL, 617925872UL,
63227947UL, 753541597UL, 100258262UL, 424125689UL, 829467248UL,
164441892UL, 370167593UL, 638783770UL, 915002648UL, 585973728UL,
637344621UL, 885039387UL, 931002066UL, 148080977UL, 120641252UL,
756963070UL, 650418703UL, 987550857UL, 674404715UL, 880865486UL,
453521763UL, 749792426UL, 178204389UL, 329742119UL, 587983440UL,
659171480UL, 766476638UL, 571515713UL, 797114270UL, 426034975UL,
955735856UL, 216003410UL, 678987148UL, 299203434UL, 465565587UL,
902734860UL, 994278977UL, 802745935UL, 157374771UL, 975082600UL,
485308849UL, 366811809UL, 83666269UL, 657397385UL, 564480749UL,
152424271UL, 533637737UL, 619370092UL, 492112859UL, 716548602UL,
679146696UL, 368223520UL, 621426508UL, 466813605UL, 849535863UL,
432658539UL, 111169964UL, 454700572UL, 679123640UL, 881298901UL,
479737438UL, 663506606UL, 718997663UL, 409456162UL, 963961946UL,
789982369UL, 669920356UL, 795136359UL, 370826525UL, 96985798UL,
852216586UL, 677138221UL, 720852371UL, 302932232UL, 314036929UL,
616221751UL, 933837728UL, 824951894UL, 304752018UL, 652622755UL,
235280030UL, 187651243UL, 509908516UL, 408245327UL, 847845699UL,
344401793UL, 488664461UL, 766052485UL, 889198917UL, 790775740UL,
520580095UL, 507556235UL, 643771617UL, 667533631UL, 498360651UL,
833572162UL, 37267990UL, 789146096UL, 512080153UL, 617850656UL,
354769670UL, 79583297UL, 835477164UL, 758357699UL, 859803242UL,
406121432UL, 623199446UL, 274024377UL, 84832848UL, 345149764UL,
306752655UL, 113847775UL, 328674813UL, 74562178UL, 410934883UL,
238205136UL, 877860895UL, 895897662UL, 960924322UL, 177990614UL,
731553581UL, 656015589UL, 23785181UL, 185050397UL, 652800241UL,
558890519UL, 582117708UL, 790171732UL, 770130758UL, 589058627UL,
412849268UL, 752594264UL, 564205145UL, 712352621UL, 71300970UL,
239806561UL, 850273242UL, 632509804UL, 642718946UL, 39199042UL,
400927136UL, 24594646UL, 694144981UL, 625367156UL, 547923081UL,
741184575UL, 382166294UL, 448874297UL, 998249728UL, 962938479UL,
455605114UL, 711694863UL, 189707921UL, 123831989UL, 228203648UL,
389461254UL, 979027199UL, 58335991UL, 86397957UL, 87697340UL,
46043291UL, 415882382UL, 645057356UL, 724730227UL, 602372245UL,
949552955UL, 44743570UL, 584254228UL, 818446040UL, 195423076UL,
449932488UL, 878340092UL, 658314381UL, 349551221UL, 277231706UL,
771355655UL, 906617008UL, 946490847UL, 931146944UL, 10231257UL,
653816011UL, 625003912UL, 147969540UL, 473005614UL, 133711548UL,
298577917UL, 287187356UL, 166528808UL, 667159115UL, 600048009UL,
484303128UL, 457083267UL, 2430560UL, 368054331UL, 411226948UL,
694778751UL, 48375354UL, 955910176UL, 154449234UL, 547461247UL,
906949232UL, 139616752UL, 778529454UL, 389832858UL, 552293467UL,
274514214UL, 324612254UL, 227095659UL, 572861032UL, 989173178UL,
402791394UL, 811027909UL, 197154919UL, 868910649UL, 140846456UL,
104456241UL, 890305312UL, 20529627UL, 466299170UL, 188638061UL,
325041514UL, 398522803UL, 102886939UL, 869794123UL, 473311022UL,
316868245UL, 992179242UL, 235376195UL, 752839615UL, 130530249UL,
724046073UL, 299317019UL, 108791875UL, 222952444UL, 985845914UL,
372143360UL, 741088251UL, 879966555UL, 258951772UL, 271643935UL,
209568706UL, 637493112UL, 406767231UL, 434704835UL, 866197272UL,
43714224UL, 662278006UL, 779814946UL, 420104596UL, 176954230UL,
904973430UL, 4387084UL, 550546216UL, 953419184UL, 320651250UL,
310502973UL, 340922755UL, 106009115UL, 911324680UL, 620825807UL,
518699507UL, 256350344UL, 157122069UL, 938636092UL, 348715365UL,
347355636UL, 785634592UL, 446845473UL, 946919543UL, 42611361UL,
788474698UL, 88641718UL, 353502244UL, 134149673UL, 540739804UL,
289550909UL, 657002599UL, 809964771UL, 375950487UL, 824072580UL,
625963950UL, 910832510UL, 484392026UL, 58309095UL, 400753025UL,
666689663UL, 223577221UL, 772707269UL, 39016003UL, 455054676UL,
875931732UL, 258974874UL, 335718753UL, 212637136UL, 972760UL,
100177014UL, 849858944UL, 64819914UL, 411247937UL, 57392195UL,
535188178UL, 210612579UL, 550070062UL, 342254099UL, 734236642UL,
794136940UL, 803786598UL, 147927969UL, 917910991UL, 173412533UL,
742393318UL, 640278966UL, 41817842UL, 71949499UL, 833602876UL,
898484009UL, 877005846UL, 91648784UL, 303958620UL, 423992696UL,
825695420UL, 585797274UL, 706139223UL, 577943675UL, 630958952UL,
204606774UL, 362658988UL, 203835608UL, 332843680UL, 993487690UL,
768820910UL, 251364139UL, 805366229UL, 254058959UL, 336582162UL,
751580073UL, 391235753UL, 133998207UL, 964096682UL, 273088160UL,
327027563UL, 502857827UL, 262465590UL, 376854499UL, 248662915UL,
244783003UL, 208631626UL, 403159597UL, 521012882UL, 544189456UL,
540178377UL, 521502561UL, 288183808UL, 961798070UL, 47828171UL,
930219980UL, 197282332UL, 284809781UL, 293643445UL, 347490754UL,
364000265UL, 786963373UL, 833699661UL, 116488712UL, 174587843UL,
591756970UL, 94657020UL, 99965809UL, 581192295UL, 276046445UL,
722468525UL, 959503365UL, 296201077UL, 764162189UL, 861384396UL,
935117676UL, 495180594UL, 620827777UL, 146189179UL, 627126867UL,
996206790UL, 537424004UL, 263050550UL, 285251044UL, 226316335UL,
571661968UL, 524878900UL, 722111469UL, 690634668UL, 586186269UL,
698491084UL, 173244528UL, 83841419UL, 254530257UL, 785827747UL,
752063841UL, 384528721UL, 812658922UL, 395887990UL, 771423271UL,
363165779UL, 858190609UL, 563508359UL, 385787253UL, 326007062UL,
480638105UL, 878397497UL, 635122081UL, 818126613UL, 287890702UL,
999857546UL, 167487288UL, 197642752UL, 888098713UL, 811185772UL,
852028205UL, 296864702UL, 603732620UL, 320934102UL, 956963679UL,
627478548UL, 893131040UL, 823463724UL, 127504547UL, 623762209UL,
947157801UL, 873869575UL, 765968120UL, 510873530UL, 780857796UL,
213377479UL, 585253570UL, 996069567UL, 960340039UL, 66382507UL,
777661393UL, 304035597UL, 543383611UL, 953229587UL, 693755724UL,
55240420UL, 569999615UL, 720013526UL, 971058558UL, 807388718UL,
926043166UL, 327869235UL, 700488647UL, 92205871UL, 157506130UL,
392494591UL, 153796275UL, 66788502UL, 655237145UL, 515211791UL,
516868783UL, 162898671UL, 797072840UL, 600703992UL, 886823839UL,
67090146UL, 741044025UL, 342375552UL, 241472381UL, 791130496UL,
73431468UL, 235797278UL, 43442398UL, 956777177UL, 331132701UL,
681272800UL, 946894727UL, 526573642UL, 278717579UL, 954910620UL,
300186695UL, 543482826UL, 919944823UL, 280947144UL, 969696185UL,
419001446UL, 85963305UL, 645862546UL, 814302269UL, 906347634UL,
585627278UL, 25360824UL, 543492913UL, 974235994UL, 128894254UL,
456461392UL, 932360993UL, 114292041UL, 777511408UL, 636555875UL,
272324303UL, 550127444UL, 596771988UL, 495556269UL, 981577578UL,
373446621UL, 990214146UL, 367200752UL, 468343165UL, 319043237UL,
854375398UL, 36697914UL, 401508259UL, 787296984UL, 105433614UL,
565151519UL, 127130900UL, 350104465UL, 445439674UL, 599436782UL,
684736924UL, 314044213UL, 714896681UL, 92274040UL, 821576871UL,
223939400UL, 959395293UL, 200546907UL, 992400155UL, 964439742UL,
98839365UL, 377630833UL, 871047820UL, 577388754UL, 296464724UL,
424983426UL, 887739941UL, 409918997UL, 102834629UL, 161564506UL,
458727439UL, 111095135UL, 95607958UL, 142354047UL, 124215638UL,
3540049UL, 117298352UL, 621107371UL, 805021821UL, 484399001UL,
460784992UL, 399083761UL, 439987571UL, 460097901UL, 878784724UL,
632495084UL, 948385881UL, 41181029UL, 990032334UL, 269318420UL,
318297692UL, 948807093UL, 179484787UL, 958518732UL, 404784912UL,
664409951UL, 202297325UL, 301740886UL, 819807830UL, 607639412UL,
651774325UL, 731394741UL, 120154231UL, 167727312UL, 22320401UL,
760761704UL, 142746798UL, 955500497UL, 729451189UL, 263005876UL,
635511914UL, 958341823UL, 512238844UL, 142738694UL, 30538523UL,
827376638UL, 135729705UL, 862985076UL, 52443102UL, 740369185UL,
124066401UL, 390577448UL, 469975588UL, 461453236UL, 68796148UL,
279516824UL, 805088083UL, 454678297UL, 574225003UL, 696052227UL,
100814231UL, 622203745UL, 539086687UL, 483745091UL, 805222033UL,
187261998UL, 135209444UL, 684147516UL, 848044861UL, 456238200UL,
516368245UL, 178340965UL, 941544853UL, 740139910UL, 91965250UL,
262390875UL, 272105460UL, 220844604UL, 100091971UL, 67207150UL,
540894960UL, 2681527UL, 71675093UL, 508717863UL, 950217765UL,
653743378UL, 222764882UL, 759804177UL, 907471138UL, 543113314UL,
901458812UL, 404056429UL, 604630301UL, 854616482UL, 364079106UL,
863729290UL, 433801803UL, 94407865UL, 518820889UL, 557697000UL,
969382657UL, 479810507UL, 61834513UL, 145682226UL, 491520411UL,
425600801UL, 138942117UL, 205286353UL, 864522652UL, 891736635UL,
859690344UL, 105791222UL, 622884576UL, 951167266UL, 464094334UL,
65903766UL, 226076997UL, 495873629UL, 650078110UL, 873966118UL,
563672894UL, 138009593UL, 830529432UL, 722973606UL, 539094778UL,
183549690UL, 23170132UL, 503974202UL, 196193101UL, 897961445UL,
753399207UL, 786459841UL, 233878900UL, 15361701UL, 854566344UL,
559388306UL, 703842860UL, 162183426UL, 849322514UL, 117414039UL,
688067847UL, 794576448UL, 615129708UL, 59802201UL, 11558417UL,
953764824UL, 462641224UL, 694976227UL, 154055963UL, 781419135UL,
475801956UL, 351995246UL, 430051978UL, 323266418UL, 593847927UL,
185038795UL, 396067544UL, 671067696UL, 788030301UL, 161567848UL,
254262376UL, 70198986UL, 984079682UL, 748474156UL, 686727210UL,
343814829UL, 105122951UL, 553059248UL, 946959644UL, 355444080UL,
793148259UL, 782572527UL, 795780377UL, 277433262UL, 979748716UL,
422111584UL, 432861740UL, 46686325UL, 344529942UL, 93673227UL,
401778097UL, 354012152UL, 228087856UL, 595609372UL, 619023093UL,
974160767UL, 468149994UL, 341257906UL, 8896849UL, 656519268UL,
101290468UL, 989535118UL, 841704737UL, 516999062UL, 7482585UL,
837300577UL, 903207437UL, 646743711UL, 636614621UL, 149277453UL,
517403977UL, 68112131UL, 481153615UL, 835733541UL, 791394994UL,
128684780UL, 704150786UL, 489514585UL, 375774275UL, 472071052UL,
102801178UL, 845353948UL, 843851827UL, 128907410UL, 92404497UL,
97238915UL, 704857829UL, 842724727UL, 98765052UL, 64299612UL,
821038107UL, 743687754UL, 533967434UL, 665155978UL, 932348853UL,
728367766UL, 634213096UL, 41046598UL, 16880415UL, 37615332UL,
762817159UL, 889851909UL, 195401134UL, 113009448UL, 844452662UL,
847658058UL, 185998099UL, 816735635UL, 46315135UL, 952857516UL,
661744101UL, 190207392UL, 875066435UL, 993329117UL, 314942619UL,
586466993UL, 507649551UL, 395600581UL, 442742053UL, 981943295UL,
116933363UL, 629192281UL, 613410275UL, 630728738UL, 574325207UL,
653660381UL, 993424868UL, 126488009UL, 605276634UL, 444570973UL,
974480359UL, 9671552UL, 506778428UL, 622905305UL, 381034490UL,
527059839UL, 607072347UL, 185390676UL, 415447157UL, 287128277UL,
640431462UL, 541702416UL, 258729739UL, 300689099UL, 989247957UL,
163888988UL, 396842024UL, 453188496UL, 616667060UL, 577956969UL,
729816471UL, 263598925UL, 676887837UL, 433351101UL, 167856213UL,
657788796UL, 977262895UL, 203971619UL, 229647870UL, 888213953UL,
604782564UL, 620166456UL, 513200120UL, 993900353UL, 856097984UL,
356120962UL, 255281119UL, 747991464UL, 126955057UL, 779179237UL,
209020451UL, 420449588UL, 371636477UL, 443847288UL, 81690115UL,
895099954UL, 100616650UL, 87457936UL, 451989258UL, 546538949UL,
999759725UL, 495510764UL, 871913555UL, 640297130UL, 622344943UL,
550948493UL, 82187067UL, 222834256UL, 531405860UL, 524745460UL,
403830413UL, 246116294UL, 620669656UL, 505542275UL, 112456207UL,
53507075UL, 832547244UL, 334953197UL, 240091705UL, 575631491UL,
858104970UL, 269302190UL, 979079355UL, 153344409UL, 22730259UL,
607517544UL, 890998694UL, 900591906UL, 196092810UL, 589873020UL,
20207709UL, 480295568UL, 398307205UL, 856732578UL, 177962598UL,
575122254UL, 864704873UL, 301759057UL, 185750808UL, 390711478UL,
927160449UL, 198993719UL, 510330397UL, 950270011UL, 322408611UL,
807510358UL, 407090870UL, 982196169UL, 758555291UL, 156197966UL,
503116563UL, 731272439UL, 508998347UL, 894077354UL, 452026104UL,
38066763UL, 480739932UL, 722904019UL, 724106327UL, 855878455UL,
154324443UL, 54074032UL, 67722398UL, 486488954UL, 282656923UL,
435195936UL, 796030559UL, 291433239UL, 495600739UL, 734214703UL,
97439052UL, 976350169UL, 863544241UL, 404275379UL, 208526828UL,
757492571UL, 153526043UL, 36094635UL, 389861581UL, 225789233UL,
542247393UL, 143126744UL, 239520501UL, 470197385UL, 68533741UL,
568846238UL, 967073468UL, 256559058UL, 944490656UL, 237070794UL,
540710244UL, 913278273UL, 174207396UL, 143308020UL, 37195129UL,
61131834UL, 769786305UL, 993490155UL, 611402276UL, 164453657UL,
856393540UL, 45852546UL, 355309981UL, 96405988UL, 576375641UL,
516867290UL, 819018887UL, 992060992UL, 199123862UL, 788617338UL,
379668129UL, 544250735UL, 525575799UL, 179545965UL, 619445966UL,
336476097UL, 586834512UL, 653962122UL, 586469617UL, 159374612UL,
912867954UL, 428403242UL, 46437843UL, 669300865UL, 377304623UL,
779155351UL, 909473846UL, 83687600UL, 506515355UL, 120130881UL,
540602724UL, 893988614UL, 460141671UL, 984992234UL, 689279387UL,
898104223UL, 614639168UL, 437444684UL, 757434862UL, 677234407UL,
590845577UL, 371971867UL, 556413066UL, 206108453UL, 671946728UL,
847072126UL, 664539851UL, 233779214UL, 76440878UL, 266602701UL,
326956757UL, 187941047UL, 361369556UL, 60567151UL, 704355983UL,
472310040UL, 483505954UL, 563314740UL, 826857022UL, 901442311UL,
110434923UL, 94228526UL, 155417002UL, 621895165UL, 947591696UL,
24864098UL, 202481527UL, 668884537UL, 780859895UL, 771546470UL,
946667087UL, 153660198UL, 88201758UL, 74434215UL, 73185619UL,
166625606UL, 974415889UL, 865025563UL, 821583140UL, 571517973UL,
227612497UL, 783143059UL, 596248347UL, 730603455UL, 85310987UL,
21407353UL, 300725495UL, 395026101UL, 91338975UL, 615172767UL,
453516111UL, 415896338UL, 936863465UL, 803681872UL, 949017213UL,
75717966UL, 348603204UL, 750350526UL, 970137129UL, 169025195UL,
744124218UL, 189228693UL, 268118190UL, 504587256UL, 901526135UL,
379736270UL, 761655504UL, 404107271UL, 534838475UL, 925745668UL,
397252797UL, 420175505UL, 536088866UL, 265711824UL, 848237514UL,
668945508UL, 715691027UL, 970766747UL, 476971438UL, 848981395UL,
638034922UL, 452191891UL, 308724914UL, 739992456UL, 210955254UL,
328034845UL, 562270648UL, 919301548UL, 917694036UL, 591962425UL,
231118116UL, 682489572UL, 353365902UL, 592213249UL, 747459415UL,
732892003UL, 950179922UL, 417155986UL, 755331814UL, 522252395UL,
301718873UL, 888654382UL, 279580286UL, 539188656UL, 794476802UL,
262105997UL, 931908138UL, 880816180UL, 564962057UL, 992715671UL,
459843319UL, 116701623UL, 431953490UL, 187633372UL, 924396145UL,
481176984UL, 540384005UL, 449901590UL, 257029697UL, 306859996UL,
661824210UL, 4220723UL, 76659649UL, 199765656UL, 938349576UL,
933008025UL, 48876217UL, 648974488UL, 891827153UL, 497589496UL,
979206154UL, 16315113UL, 715728406UL, 362171120UL, 811623383UL,
542403328UL, 246843546UL, 897781936UL, 87783263UL, 224902048UL,
994087591UL, 744299596UL, 319307715UL, 804783088UL, 26189436UL,
126826271UL, 453873042UL, 340461036UL, 876010629UL, 622163728UL,
951605077UL, 172865143UL, 796434605UL, 378995927UL, 691303607UL,
532890040UL, 257105406UL, 83855237UL, 766600696UL, 570242669UL,
43171649UL, 870026555UL, 915352607UL, 734066974UL, 786477938UL,
422947340UL, 990558653UL, 689514297UL, 739439624UL, 168612786UL,
364927034UL, 790844229UL, 400428821UL, 395795141UL, 436281392UL,
539376824UL, 884789948UL, 239956204UL, 422631857UL, 471944516UL,
505509754UL, 315246163UL, 970029261UL, 184705102UL, 39568268UL,
143608503UL, 808081500UL, 341516242UL, 39925808UL, 978673002UL,
92472680UL, 931205935UL, 583916194UL, 952653347UL, 69583408UL,
312342483UL, 683607437UL, 834787494UL, 57668780UL, 128983670UL,
226611733UL, 485013719UL, 224129103UL, 290173239UL, 915885UL,
780125782UL, 177215657UL, 14120981UL, 39708229UL, 620293954UL,
125392995UL, 52697849UL, 493081824UL, 323037998UL, 937387603UL,
443104891UL, 451033090UL, 814778525UL, 166139459UL, 590088570UL,
811882102UL, 319791159UL, 541245418UL, 774279972UL, 439641256UL,
238846081UL, 704326918UL, 88204835UL, 276178934UL, 844447970UL,
335046949UL, 966150943UL, 821760774UL, 232463876UL, 683175564UL,
866610819UL, 906405524UL, 7493430UL, 802842231UL, 265828358UL,
893303162UL, 219189249UL, 632914422UL, 988936438UL, 23095614UL,
794104135UL, 636117346UL, 798676643UL, 506793571UL, 232185803UL,
731061296UL, 936825753UL, 17407290UL, 952263996UL, 592880054UL,
531611742UL, 636198807UL, 985944805UL, 503748467UL, 395111166UL,
943712708UL, 419069942UL, 180221648UL, 102371364UL, 401016464UL,
543921100UL, 17727757UL, 640622993UL, 458272198UL, 767387757UL,
509082505UL, 188935936UL, 602307389UL, 686763332UL, 950645394UL,
420318554UL, 436731949UL, 799875209UL, 802343321UL, 511813608UL,
175754777UL, 973982638UL, 648140832UL, 753642478UL, 983074912UL,
247774260UL, 664675316UL, 893669846UL, 328278980UL, 512353405UL,
75868999UL, 953402374UL, 527461317UL, 464455828UL, 955652323UL,
303859794UL, 60362726UL, 582011704UL, 673839505UL, 109906018UL,
723799492UL, 664927299UL, 515371609UL, 115980452UL, 598386918UL,
768023976UL, 825862098UL, 730091328UL, 970285038UL, 993534324UL,
743833527UL, 242175212UL, 764602503UL, 941269463UL, 699715183UL,
737330047UL, 386865729UL, 936717772UL, 223305457UL, 496325472UL,
139921267UL, 293499475UL, 482110580UL, 161120226UL, 82001641UL,
936370548UL, 258101980UL, 180687636UL, 368515462UL, 221387533UL,
201666311UL, 976635059UL, 444312098UL, 313333969UL, 33663185UL,
244946352UL, 213904073UL, 391092225UL, 613588649UL, 94311902UL,
640165412UL, 251003822UL, 818123803UL, 185090719UL, 972539439UL,
387377028UL, 273138809UL, 36455803UL, 628506913UL, 54785929UL,
999365662UL, 180861760UL, 862629497UL, 881821469UL, 376262322UL,
259867519UL, 865886855UL, 831033323UL, 338892937UL, 995274142UL,
868666194UL, 31660996UL, 553099801UL, 614561392UL, 137616163UL,
500790739UL, 367549208UL, 735211355UL, 53090149UL, 525494811UL,
478456524UL, 713156908UL, 659381923UL, 847878828UL, 774348384UL,
601311628UL, 132659001UL, 952699717UL, 198097476UL, 373698986UL,
863518977UL, 662652068UL, 625085394UL, 429304307UL, 205151173UL,
81606193UL, 200759438UL, 215154910UL, 545614152UL, 249435189UL,
420125300UL, 17493549UL, 11770233UL, 814380300UL, 227887570UL
};
unsigned long ulMod( unsigned long ulNumber )
{
int i;
unsigned __int64 ui64Temp, ui64Mod;
ui64Mod = gulPop[0] % ulNumber;
/**********************************************************/
/* The multiplication in this loop can be done away with */
/* if the input number array is in binary format instead */
/* of base 10 format. We can have a union, and place the */
/* mod result in the most significant portion of our #. */
/**********************************************************/
for ( i = 1; i < 3145; i++ )
{
ui64Temp = ui64Mod * 1000000000ui64 + gulPop[i];
ui64Mod = ui64Temp % ulNumber;
}
return ( unsigned long ) ui64Mod;
}
If the number were expressed in hex rather than decimal base, I would not
even need the multiplication. This is faster than division.
>
> Yes, but this is after the first division. That first division
>is going to take time proportional to the size (in bits) of your number.
>
>: >Standard factoring algorithms are FAR faster than this one would be.
>: >And can handle *much* larger numbers with reasonable computing power.
>
>: Absolutely agreed. There may be some smart folks out there that can
>: see some useful purpose for the math involved however, or it may be
>: useful for factoring in certain bands.
>
> Until it becomes faster than trial division, it is unlikely
>to be useful as anything other than the answer to exercise 4.5.4.3.
Agreed.
>: >Ben Tilly
>: >
>: >(If Microsoft uses algorithms like this, that would explains some
>: >things...)
>: It certainly would not explain how they became the most powerful and
>: influential software company in the world.
>
> Announcing something that is at best 25% slower, and measurably
>less useful, than the slowest algorithm in use as an advance seems to
>be precisely what makes Microsoft both extremely profitable and hideously
>annoying. Though I thought that claiming that long division was orders
>of magnitude faster than long division was a classic worthy of the master,
>and much more Microsoftian.
I never claimed it was an advance, nor did I say that it was faster than
any existing algorithm. I did want to explore the speed of the algorithm,
because when I originally posted, I had no idea how it would perform when
scaled up. Several mathematically inclined individuals did send me
friendly, courteous email messages to explain the behavior in terms that
I could understand. My last line was saying that IF MS used algorithms
that were inefficient, they would not be successful. You apparently missed
my meaning.
>: --
>: The opinions expressed in this message are my own personal views
>: and do not reflect the official views of Microsoft Corporation.
>: In fact, I'm just a subcontractor, not an employee, so pull in your claws.
>
>--
>David M Einstein | Lord, grant me the companionship of those who seek | the truth, and
protection from those
--
JUD MCCRANIE
On 25 Feb 96 03:04am, DIK T WINTER wrote to ALL:
DTW> Ben, you ought to know better. But Dann's response is off-track too
DTW> (he just replaces division by taking the mod). See Knuth, Vol. 2, I
Whan that book was written, division and Mod operations were
slow. The binary method (when I implemented it) was quite a bit
slower than the "modern" Euclid method. A factor of 3.8 slower,
I think it was. It was written in a HLL, and a assembler could
make the binary method better than my implementation, but on
modern computers I think the binary method will still be slower.
DTW> See? No division, only by 2 (which is much faster than true division
DTW> on a binary machine, because it is a shift). Knuth discusses
DTW> the merits of both Euclids and this (binary) algorithm at length. Both
DTW> are similar in time complexity and worst case. Euclids is worst case
DTW> if the two numbers are succesive Fibonacci numbers; off-hand I do not
DTW> know the worst case for the binary algorithm, but it is similar.
I think the analysis is the same, but I'm not sure.
Jud McCranie jud.mc...@swsbbs.com
... Happiness is a composite number with a small factor.
* Silver Xpress V4.3 SW20178
David M Einstein
: In article <Dn9GK...@world.std.com>, Dei...@world.std.com says...
: >
: >: >Ben Tilly
: >: >
: >: >(If Microsoft uses algorithms like this, that would explains some
: >: >things...)
: >: It certainly would not explain how they became the most powerful and
: >: influential software company in the world.
: >
: > Announcing something that is at best 25% slower, and measurably
: >less useful, than the slowest algorithm in use as an advance seems to
: >be precisely what makes Microsoft both extremely profitable and hideously
: >annoying. Though I thought that claiming that long division was orders
: >of magnitude faster than long division was a classic worthy of the master,
: >and much more Microsoftian.
: I never claimed it was an advance, nor did I say that it was faster than
: any existing algorithm. I did want to explore the speed of the algorithm,
: because when I originally posted, I had no idea how it would perform when
: scaled up. Several mathematically inclined individuals did send me
: friendly, courteous email messages to explain the behavior in terms that
: I could understand. My last line was saying that IF MS used algorithms
: that were inefficient, they would not be successful. You apparently missed
: my meaning.
I apologize, I was extremely rude.
: --
: The opinions expressed in this message are my own personal views
: and do not reflect the official views of Microsoft Corporation.
: In fact, I'm just a subcontractor, not an employee, so pull in your claws.
--
David M Einstein | Lord, grant me the companionship of those who seek | the truth, and protection from those who have found
Benjamin J. Tilly
d...@cwi.nl (Dik T. Winter) writes:
> In article <4gl686$2...@news.microsoft.com> a-c...@microsoft.com (Dann Corbit) writes:
> > In article <4gdgpe$k...@dartvax.dartmouth.edu>, Benjamin...@dartmouth.edu says...
> > >Not so fast. In order to find the GCD you have to DIVIDE the product by
> > >your number. How long does this division take??? About the size of your
> > >number!
>
> Ben, you ought to know better. But Dann's response is off-track too (he
> just replaces division by taking the mod). See Knuth, Vol. 2, I think.
> From the top of my head (and absolutely untested):
> unsigned gcd(unsigned i, j)
> {
> unsigned tmp, i2 = 0, j2 = 0;
> if(i == 1 || j == 1) return 1;
> if(i != 0) while(!(i & 1)) { i >>= 1; i2++;}
> if(j != 0) while(!(j & 1)) { j >>= 1; j2++;}
> if(i > j) { tmp = i; i = j; j = tmp;}
> while(i != 0) {
> j -= i;
> if(j != 0) while(!(j & 1)) j >>= 1;
> if(i > j) { tmp = i; i = j; j = tmp;}
> }
> return j + 1 << (i2 < j2 ? i2 : j2);
> }
>
> See? No division, only by 2 (which is much faster than true division
> on a binary machine, because it is a shift). Knuth discusses
> the merits of both Euclids and this (binary) algorithm at length. Both
> are similar in time complexity and worst case. Euclids is worst case if
> the two numbers are succesive Fibonacci numbers; off-hand I do not know
> the worst case for the binary algorithm, but it is similar.
>
> { From a purely mathematic viewpoint, there is of course no difference
> between a division by 2 and a division by any other number. For a
> computer scientists viewpoint there is a huge difference, unless he
> is a Soviet computer scientist working with the, now defunct, base 3
> computer (Setun).}
>
I am a mathematician, so to me there is no difference...
(In fact later, possibly even in the same post though I think not, I
explained why it is that you cannot do more than a constant factor
better than division gives you.)
> Still the question and the response are not in any way related to the
> question whether the method is feasable or not. Doing a MOD (or GCD)
> of a large product of primes and another (smaller) number is in time
> complexity related to the size of the largest number (as Ben states and Dann
> implicitly states when he is talking about time needed reading numbers).
[..]
> > >(If Microsoft uses algorithms like this, that would explains some
> > >things...)
>
> I think, Ben, that this is uncalled for. Posting from microsoft in no
> way should involve microsoft in the postings (as my posting this from
> cwi should in no way involve cwi in the contents).
>
I agree that it is a cheap shot. However I was getting irritated that
when he first asked about this method, I sent him an e-mail explanation
of why it did not work. And then when he kept on posting for a bit
about how good he thought that this method was, I just could not
resist.
I should not have posted that.
> > It certainly would not explain how they became the most powerful and
> > influential software company in the world.
>
> On the other hand, Dann, being the most powerful and influential does
> not make it necessarily the best.
>
> Can we dispose off affiliations?
Ben Tilly
Robert Johnson
numt...@tiac.net wrote:
>a-c...@microsoft.com (Dann Corbit) wrote:
>>I calculate that 4000 cd-roms could contain enough factors
>>to completely factor a 100 bit number. Further, with 4000
>
>Not even close. With N = 10^100 the product of the primes needed
>is about e^(10^50). If one could store each bit (somehow)
>in a space the size of the Planck length, there would not be
>enough space in the entire universe to hold the number.
A 100 bit number is less than 2^100, not 10^100. Thus, the product of
primes needed is exp(2^50) which has about 1.62433e15 bits. A CD-ROM
holds 650 MB which is about 5452595200 bits. This means that about
300000 CD-ROMs could hold the appropriate LCM. Thus, it is physically
possible to hold this number. Feasibility is a different matter.
Rob Johnson
Apple Computer, Inc.
rjoh...@apple.com
Dann Corbit
>
>
>On 25 Feb 96 03:04am, DIK T WINTER wrote to ALL:
>
> DTW> (he just replaces division by taking the mod). See Knuth, Vol. 2, I
>Whan that book was written, division and Mod operations were
>slow. The binary method (when I implemented it) was quite a bit
>slower than the "modern" Euclid method. A factor of 3.8 slower,
>I think it was. It was written in a HLL, and a assembler could
>make the binary method better than my implementation, but on
>modern computers I think the binary method will still be slower.
>
>
> DTW> See? No division, only by 2 (which is much faster than true division
> DTW> on a binary machine, because it is a shift). Knuth discusses
> DTW> the merits of both Euclids and this (binary) algorithm at length. Both
> DTW> are similar in time complexity and worst case. Euclids is worst case
> DTW> if the two numbers are succesive Fibonacci numbers; off-hand I do not
> DTW> know the worst case for the binary algorithm, but it is similar.
>
>I think the analysis is the same, but I'm not sure.
>
>
>Jud McCranie jud.mc...@swsbbs.com
>
>... Happiness is a composite number with a small factor.
> * Silver Xpress V4.3 SW20178
>
is "tiny" in respect to the other. Whatever remainder I have will be less
than my test number to factor. Hence accumulation of the running remainder
is very simple.
Product of primes consists of words 1 to n.
Most significant word is word 1, least is n.
Here is our big product of primes number:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+
|1| | | | | | | | | | | | | | | | | | ...|n|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+
Input to test is one word. Here is our test word:
+-+
|w|
+-+
1. Take the mod of the first two words of our product of primes
with our test word.
2. Take the remainder as the most significant word and concantenate
it with the third word from our big prime product.
3. Take the mod of the newly formed number with our test word.
4. Take the remainder as the most significant word and concantenate
it with the next word from our big prime product.
5. Go to 3 until we reach n.
In the sample I provided, the modulus of a 28000+ digit number with
a 32 bit integer is found in 3145 64-bit integer modulus operations.
If the number were expressed in Hexadecimal format, then the 3145
integer multiplications would not be necessary.
Dann Corbit
{ Big snip}
>However I was getting irritated that
>when he first asked about this method, I sent him an e-mail explanation
>of why it did not work. And then when he kept on posting for a bit
>about how good he thought that this method was, I just could not
>resist.
method. Most people responding seem to think that I did imply that, but
it may be just my enthusiasm being misunderstood. I have a bachelor's
degree in Numerical Analysis, but I am not a mathematician (as my many
blunders in this newsgroup will attest). For me, math is a hobby, and a
hobby for which I show "puppy-dog" enthusiasm. Many things that appear
to be 'discoveries' to me will probably be old-hat to the real mathematicians
who subscribe to this news group. I realize that I am very much the student
in this group, and recognize the superiority of the teachers. Nevertheless,
my enthusiasm will never wane, and I will no doubt make lots of blundering
posts concerning things that I want to discover.
By the way, I once had a cat named "PI".