Re: 128 or 96 bit integer types?
On Jul 29, 11:35 pm, Tim Roberts [EMAIL PROTECTED] wrote: John DeRosa [EMAIL PROTECTED] wrote: On Sat, 28 Jul 2007 00:19:02 -0700, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: For example, how many ways can you put 492 marbles into 264 ordered bins such that each bin has at least 1 marble? The answer 66189415264331559482776409694993032407028709677550 59629130019289014193777349831417543311612293951363 4124491233746912456893016976209252459301489030 You missed that blue one in the corner... Actually, the blue one in the corner wasn't missed, it was deliberately omitted. When you add the restriction that each bin must contain at least one marble, the number of partitions of depth items into width bins is comb(depth-1,width-1). So comb(491,263) IS, in fact, the correct answer even though the marble count seems to be wanting. He lost that one to a talented 12-year-old with a keen eye and a well-balanced steelie... -- Tim Roberts, [EMAIL PROTECTED] Providenza Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
Paul Rubin wrote: [EMAIL PROTECTED] [EMAIL PROTECTED] writes: has 146 digits. And that's just the begining. The above actually represents a polynomial with 264 terms, the exponents of which range from 0 to 492. One of those polynomials can have over 5 decimal digits when solved. You should use gmpy rather than python longs if you're dealing with numbers of that size. Python multiplication uses a straightforward O(n**2) algorithm where n is the number of digits. That's untrue since quite a while. CPython now uses Karatsuba-multiplication if the number of digits is larger than a certain threshold. Karatsuba is O(n**(log(3) / log(2)). This is the best way for up to a few hundred or maybe a few thousand digits. After that, it's better to use more complicated FFT-based algorithms which are O(n log n) despite their increased constant overhead. Gmpy does this. Karatsuba is still slower than these algorithms, but only if you have quite a big number of digits. Of course the core of your argument remains valid: CPython is not up to providing extremely good big integer arithmetic, so if you have extreme needs, you shouldn't use the builtin longs. Cheers, Carl Friedrich Bolz -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
On Jul 28, 3:34 am, David H Wild [EMAIL PROTECTED] wrote:
In article [EMAIL PROTECTED],
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
For example, how many ways can you put 492 marbles into
264 ordered bins such that each bin has at least 1 marble?
The answer
66189415264331559482776409694993032407028709677550
59629130019289014193777349831417543311612293951363
4124491233746912456893016976209252459301489030
has 146 digits.
What on earth made you think of that question?
Reearch on the Collatz Conjecture. Any Collatz
sequence can be described by a non-empty list of
integers 0. Such as
[1,1,1,1,1,1,1,1]
[1,2,3,4,5,6]
[1009873,74396597698765,2,240895734075]
I proved that ANY posible list must exist on the
Collatz graph infinitely many times. The polynomials
derived from such a list identify the first occurence
of the set of infinite solutions.
For a sequence in 3n+C to be a loop cycle, it is
necessary (but not sufficient) for a power of 2
(2**p) to be congruent to a power of 3 (3**q) modulo
a divisor of C.
For example, the congruence classes of 2**p mod 41 are
(1,2,4,5,8,9,10,16,18,20,21,23,25,31,32,33,36,37,39,40)
the congruence classes of 3**q mod 41 are
(1,3,9,14,27,32,38,40)
The only classes they have in common are: {1,9,32,40}
so from this table,
p or q 2p (mod 41) 3q (mod 41)
0 1 1
1 2 3
2 4 9
3 827
41640
53238
62332
7 514
810 1
920 3
10 40 9
11 3927
12 3740
13 3338
14 2532
15914
16 18 1
17 36 3
18 31 9
19 2127
20140
only those p,q pairs (such as p=20 q=8) that have
matching congruence classes mod 41 can be potential
loop cycles in 3n+41.
This can be translated to the marble problem by asking
how many ways are there to make a list of q non-zero
positive integers that sum to p?
Of the 50388 ways, 8 of them have integer solutions
and because these 8 are cyclic permutaions, they
represent the same loop cycle
[2,1,3,1,2,1,1,9] 1
[1,3,1,2,1,1,9,2] 11
[3,1,2,1,1,9,2,1] 37
[1,2,1,1,9,2,1,3] 19
[2,1,1,9,2,1,3,1] 49
[1,1,9,2,1,3,1,2] 47
[1,9,2,1,3,1,2,1] 91
[9,2,1,3,1,2,1,1] 157
To actually answer you question, there is a known loop
cycle in 3n+85085 for which p=492 and q=264. If there is
one solution, there must be at leats 263 others (the
cyclic permutations), but to brute force search for any
others would require enumerating the answer to how many
ways can 492 marbles be put in 264 bins such that each
bin has at least 1 marble.
--
David Wild using RISC OS on broadbandwww.davidhwild.me.uk
--
http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
In article [EMAIL PROTECTED], [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: To actually answer you question, there is a known loop cycle in 3n+85085 for which p=492 and q=264. If there is one solution, there must be at leats 263 others (the cyclic permutations), but to brute force search for any others would require enumerating the answer to how many ways can 492 marbles be put in 264 bins such that each bin has at least 1 marble. Thank you very much. I am awestruck. -- David Wild using RISC OS on broadband www.davidhwild.me.uk -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote: So I never let the age of the universe intimidate me. +1 QOTW. -- Tim Roberts, [EMAIL PROTECTED] Providenza Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
John DeRosa [EMAIL PROTECTED] wrote: On Sat, 28 Jul 2007 00:19:02 -0700, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: For example, how many ways can you put 492 marbles into 264 ordered bins such that each bin has at least 1 marble? The answer 66189415264331559482776409694993032407028709677550 59629130019289014193777349831417543311612293951363 4124491233746912456893016976209252459301489030 You missed that blue one in the corner... He lost that one to a talented 12-year-old with a keen eye and a well-balanced steelie... -- Tim Roberts, [EMAIL PROTECTED] Providenza Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
On Jul 28, 12:30 am, Tim Roberts [EMAIL PROTECTED] wrote: [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: On Jul 27, 1:27 pm, Peter Otten [EMAIL PROTECTED] wrote: Robert Dailey wrote: Is there build-in or third party support for large integer types, such as 96 or 128 bits in size? I require such large sizes for precision issues (nanoseconds). Thanks. SECOND = 10**9 YEAR = 365*24*60*60 2**128/SECOND/YEAR 10790283070806014188970L What are you measuring? The age of the universe? In nanoseconds? :-) Well, 2**96 would only be 2512308552583 years. Yes, but that's still roughly 100 times the estimated age of the universe. Yeah, I know. I thought it was so obvious I didn't need a :-). But _I_ won't question the need for numbers that large. That's how I got into Python in the first place, looking for Big Arithmetic. And I've been very happy with it. Especially compared to the competition. Would you believe that new F# language from Microsoft doesn't even have an exponentiation operator? It has a power function for floats, but not for Big Integers. Completely worthless. Some very simple questions can have very big answers. For example, how many ways can you put 492 marbles into 264 ordered bins such that each bin has at least 1 marble? The answer 66189415264331559482776409694993032407028709677550 59629130019289014193777349831417543311612293951363 4124491233746912456893016976209252459301489030 has 146 digits. And that's just the begining. The above actually represents a polynomial with 264 terms, the exponents of which range from 0 to 492. One of those polynomials can have over 5 decimal digits when solved. So I never let the age of the universe intimidate me. Of course, I can't solve ALL the polynomials. Gotta be a bit selective. :-) -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
[EMAIL PROTECTED] [EMAIL PROTECTED] writes: has 146 digits. And that's just the begining. The above actually represents a polynomial with 264 terms, the exponents of which range from 0 to 492. One of those polynomials can have over 5 decimal digits when solved. You should use gmpy rather than python longs if you're dealing with numbers of that size. Python multiplication uses a straightforward O(n**2) algorithm where n is the number of digits. This is the best way for up to a few hundred or maybe a few thousand digits. After that, it's better to use more complicated FFT-based algorithms which are O(n log n) despite their increased constant overhead. Gmpy does this. -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
In article [EMAIL PROTECTED], [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: For example, how many ways can you put 492 marbles into 264 ordered bins such that each bin has at least 1 marble? The answer 66189415264331559482776409694993032407028709677550 59629130019289014193777349831417543311612293951363 4124491233746912456893016976209252459301489030 has 146 digits. What on earth made you think of that question? -- David Wild using RISC OS on broadband www.davidhwild.me.uk -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
On Jul 28, 2:28?am, Paul Rubin http://[EMAIL PROTECTED] wrote: [EMAIL PROTECTED] [EMAIL PROTECTED] writes: has 146 digits. And that's just the begining. The above actually represents a polynomial with 264 terms, the exponents of which range from 0 to 492. One of those polynomials can have over 5 decimal digits when solved. You should use gmpy rather than python longs if you're dealing with numbers of that size. Python multiplication uses a straightforward O(n**2) algorithm where n is the number of digits. This is the best way for up to a few hundred or maybe a few thousand digits. After that, it's better to use more complicated FFT-based algorithms which are O(n log n) despite their increased constant overhead. Gmpy does this. I actually do use gmpy. Great stuff. But one thing I learned about gmpy is to never use literals inside a loop. Otherwise the mpz coercion has to be done every time and that kills performance. So you would do something like import gmpy ONE = gmpy.mpz(1) TWO = gmpy.mpz(2) TWE = gmpy.mpz(3) n = gmpy.mpz(2**177149-1) while n ONE: if n % TWO == 1 n = TWE*n + ONE else: n = n/TWO -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
On Sat, 28 Jul 2007 00:19:02 -0700, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: For example, how many ways can you put 492 marbles into 264 ordered bins such that each bin has at least 1 marble? The answer 66189415264331559482776409694993032407028709677550 59629130019289014193777349831417543311612293951363 4124491233746912456893016976209252459301489030 You missed that blue one in the corner... -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
On Fri, 27 Jul 2007 16:45:05 +, Robert Dailey wrote: Is there build-in or third party support for large integer types, such as 96 or 128 bits in size? Yes there is, just use integer values. If it don't fit into an `int` it gets promoted to a `long`. Python `long`\s are only bounded by available memory. In [59]: 2**128 Out[59]: 340282366920938463463374607431768211456L Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
Robert Dailey wrote: Is there build-in or third party support for large integer types, such as 96 or 128 bits in size? I require such large sizes for precision issues (nanoseconds). Thanks. SECOND = 10**9 YEAR = 365*24*60*60 2**128/SECOND/YEAR 10790283070806014188970L What are you measuring? The age of the universe? In nanoseconds? :-) Peter -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
On Jul 27, 1:27 pm, Peter Otten [EMAIL PROTECTED] wrote: Robert Dailey wrote: Is there build-in or third party support for large integer types, such as 96 or 128 bits in size? I require such large sizes for precision issues (nanoseconds). Thanks. SECOND = 10**9 YEAR = 365*24*60*60 2**128/SECOND/YEAR 10790283070806014188970L What are you measuring? The age of the universe? In nanoseconds? :-) Well, 2**96 would only be 2512308552583 years. Peter -- http://mail.python.org/mailman/listinfo/python-list
Re: 128 or 96 bit integer types?
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote: On Jul 27, 1:27 pm, Peter Otten [EMAIL PROTECTED] wrote: Robert Dailey wrote: Is there build-in or third party support for large integer types, such as 96 or 128 bits in size? I require such large sizes for precision issues (nanoseconds). Thanks. SECOND = 10**9 YEAR = 365*24*60*60 2**128/SECOND/YEAR 10790283070806014188970L What are you measuring? The age of the universe? In nanoseconds? :-) Well, 2**96 would only be 2512308552583 years. Yes, but that's still roughly 100 times the estimated age of the universe. -- Tim Roberts, [EMAIL PROTECTED] Providenza Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
