128 or 96 bit integer types?

R

Robert Dailey

Hi,

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.
 
M

Marc 'BlackJack' Rintsch

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
 
P

Peter Otten

Robert said:
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.
10790283070806014188970L

What are you measuring? The age of the universe? In nanoseconds?

:)

Peter
 
M

mensanator

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 50000 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. :)
 
P

Paul Rubin

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 50000 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.
 
M

mensanator

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
 
J

John DeRosa

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...
 
C

Carl Friedrich Bolz

Paul said:
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
 
C

Carl Friedrich Bolz

Paul said:
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
 
M

mensanator

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 8 27
4 16 40
5 32 38
6 23 32
7 5 14
8 10 1
9 20 3
10 40 9
11 39 27
12 37 40
13 33 38
14 25 32
15 9 14
16 18 1
17 36 3
18 31 9
19 21 27
20 1 40

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.
 
D

David H Wild

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.
 
M

mensanator

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top