31

The original binary search algorithm in the JDK used 32-bit integers and had an overflow bug if (low + high) > INT_MAX (http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html).

If we rewrote the same binary search algorithm using (signed) 64-bit integers, can we assume that low + high will never exceed INT64_MAX because it's physically impossible to have 10^18 bytes of memory?

When using (signed) 64-bit integers to represent physical quantities, is it reasonable to assume underflow and overflow can't happen?

13
  • 4
    Look at any physical phenomenon that has an associated irrational number. Circles and pi for example. Floating point numbers are inherently rational, thus you cannot perfectly represent it without error. Feb 24, 2015 at 1:26
  • 92
    The number of atoms in the sun is approximately 1.2e57, which fits in a 190 bit unsigned integer. By contradiction, 64 bits cannot be large enough to represent any physical quantity.
    – user22815
    Feb 24, 2015 at 5:41
  • 6
    Your question title is misleading. You should ask "are there quantities for which one might expect an application using a sorted array of size bigger than 2^64?"
    – Doc Brown
    Feb 24, 2015 at 12:11
  • 7
    or the number of yoctoseconds since you started reading this comment.
    – Jodrell
    Feb 24, 2015 at 14:15
  • 4
    There was a time when everyone thought there are never gonna be 2^32 computer connected to each other. You don't want your atoms to have to use NAT, do you?
    – Sebb
    Feb 24, 2015 at 22:10

10 Answers 10

58

The short answer is no. However, for some applications your assumption might be correct.

Assuming a signed int, 2^63, with commas added for some clarity, = 9,223,372,036,854,775,808. So it's roughly 9 * 10^18. 10^18 is an "Exa".

Wikipedia says "As of 2013, the World Wide Web is estimated to have reached 4 zettabytes.[12]", which is 4000 Exabytes. Therefore, the WWW is roughly 400 times larger than 2^63 bytes.

Therefore, there is at least one physical quantity that is much larger than a signed (or unsigned) 64 bit integer. Assuming that your units are bytes. If your units were something much larger, like GigaBytes, then you'd be o.k., but your precision of measurement would be low.

For another example, consider far away galaxies. The Andromeda Galaxy is actually one of the close ones, and it is 2.5 * 10^6 light years away. If your units were miles, that would be 14.5 * 10^18, more than a 64 bit signed integer. Now, obviously it depends on the units you use for your measurements, but some galaxies are way further away than Andromeda. (The furthest known one is 13 * 10^9 L.Y. away.) Depending on the precision you want for your measurement, it could overflow a 64 bit integer.

(Added) Yes, miles are a lousy unit for astronomical distance. A more normal unit might be an Astronomical Unit, roughly 93 million miles. Using that unit of measurement, the furthest known galaxy is roughly 10^15 A.U. (if my math is right), which would fit into a 64 bit int. However, if you wanted to also measure the distance to the Moon, to nearby orbiting satellites, that unit is too large.

One more example from electronics: the Farad (F), a unit of capacitance. Large capacitors range up to 5kF. And this number will likely increase over time as Hybrid cars, "smart grids", etc. improve. Once can measure capacitance as small as 10^-18 F. So the overall range in "real" capacitance that we can measure today is 5*10^21, larger than a 64 bit integer.

12
  • 3
    All of this is true, but on a practical point of view we can question the point of measuring Andromeda's galaxy distance from the Milky Way in miles (where exactly are the point of references?) or the entire WWW in bytes (at this precision, it changes every millisecond)
    – Jivan
    Feb 24, 2015 at 10:26
  • 45
    @Jivan On a practical point of view I can see no reason why you would ever need to address more than 640kB of memory. Surely its more than you would EVER need.
    – ArTs
    Feb 24, 2015 at 10:39
  • 2
    Another drawback to measuring astronomical distances in miles: You're liable to get thwapped with a cat. Feb 24, 2015 at 12:02
  • 2
    @Jivan Good point. That reminds me of Richard Feynman ranting about the silliness of summing the temperature of a group of stars. I see why you would want the average, the minimum, the maximum, but the sum? What physical significance is that?
    – piojo
    Feb 24, 2015 at 16:09
  • 6
    @piojo - admittedly the sum comes in handy when computing the mean. Feb 24, 2015 at 19:09
21

You don't even need to go cosmic when combinatorics are involved. There are 2^95 possible deals in a game of bridge and that's on the small side of complexity.

4
  • One might wonder if that counts as a "physical quantity". Feb 25, 2015 at 0:27
  • 2
    On the other hand, combinatorics involved in chemistry or mathematics would qualify as being "physical".
    – rwong
    Feb 25, 2015 at 3:12
  • @PaulDraper if you got enough decks of cards to layout on the ground all those deals it would be physical. Then you'd have even more than 2^95 cards involved.
    – Brad
    Feb 25, 2015 at 17:29
  • 1
    @Brad, I think the OP is asking for a quantity that "exists" (okay, existence is a fuzzy concept). 2^95 cards that satisfy a mathematical concept do not exist (call Guinness if they do). It's hard to say what "counts" and what doesn't. This answer just doesn't satisfy my squishy notion of a physical quantity. Feb 25, 2015 at 17:36
17

The most relevant physical quantity for your question is computer RAM.

Windows Server 2012 supports up to 4 TB of physical memory. That's 242 bytes. If RAM capacities continue doubling about every year, then in only 17 years from now "Windows Server 2032" will support 262 bytes of physical memory, at which time your low + high will reach 263 - 2 and kiss the max signed 64-bit integer.

I hope no safety-critical systems fail, having assumed 64 bits will always be enough.

For a slightly more general use, the most relevant physical quantity is memory address space. (It's useful to have much a larger address space than physical memory, e.g. to put many stacks in memory, all with room to grow.) Current x86-64 implementations support 48 bit virtual addresses, so we have only 14 years before these CPUs reach the 262 byte address-space limit.

And then there's distributed shared memory "where the (physically separate) memories can be addressed as one (logically shared) address space".

13
  • 4
    +1 Your answer is almost exactly correct, except that certain types of today's software are already encountering memory addresses in the range of 0xFFFFFFFFxxxxxxxx (i.e. the higher half ), for example the operating system or device drivers.
    – rwong
    Feb 24, 2015 at 7:22
  • 2
    @SiqiLin probably not as far as personal computing is concerned. However, the distributed shared memory, or the DGAS (mentioned in the article) are real; supercomputers have been operating in that style for years, and it is possible that it might become the norm for multi-national cloud computing infrastructure. Apparently, the typical software code written by the typical programmer won't be running in such an environment - unusual environments run unusual (i.e. infrastructural) software. But a fraction of P.SE readers might just land on such a career track; just in case.
    – rwong
    Feb 24, 2015 at 7:42
  • 1
    @Joshua: With current technology (32 GB DDR4) that would be 7m or 23 ns for light to travel, which seems perfectly in line with modern CAS latencies. If you push it to the Landauer's principle extreme, with the density of silicon you get 31 nm or 10^-16 seconds for the physical limit. That doesn't seem too crazy... well, maybe just a little.
    – Charles
    Feb 24, 2015 at 20:50
  • 3
    @Joshua That's a technological limit, not a physical one. (As in, the problem is that we don't know how to do it practically, not that some physical law prohibits it.) Therefore, while relevant this week, it could change at any moment with some new breakthrough. 60 or so years ago, people would have made comments very similar to yours, about 50 kilobytes of memory being considered RAM, on the grounds that hand-wound wire coils then used as parts of memory cores not only could get only so small and still function, but required space between them to avoid EM crosstalk. Feb 24, 2015 at 22:10
  • 2
    I remember when 24 bits of address space (16 megabytes) was more than anyone would ever need - or be able to afford. :-) Feb 25, 2015 at 4:14
10

Is it reasonable to assume that any physical quantity can be represented by a 64-bit integer without overflow or underflow?

Not exactly. There are plenty of numbers that are both bigger and smaller than that, which is why we have floating point numbers. Floating point numbers trade off lesser precision for better range.

In the specific example that you cited, it is highly unlikely that you would ever need a number that's larger than that. 64 bits corresponds to roughly 18 quintillion elements. But never say never.

7

Your assumption won't handle physical quantities that can only be represented by floating point numbers. And even if you decided to scale all numbers, say by multiplying all numbers by 10000 (so the values are still integers but can be represented in ten-thousandths), this scheme still fails for numbers very close to zero, for example the electron mass (9.1094 * 10⎻³¹ kg).

That is a very real (and extremely small) physical quantity, here are some more you're going to have trouble with. And if you argue that's not a real physical quantity (even though it is in kg), consider:

10 kg (obviously physical quantity)
1 kg (same)
10⎻² kg (1/100 kg, or about 1/3 ounce) (also quite real)

So you see where I'm going with this. The last one you can't handle either.

Of course, you could have a special field within the number to scale an integer portion up or down by a variable multiplier; gee now you just invented floating point.

5
  • 1
    But you can assign a minimum physical value (IIRC, for mass it was the mass equivalent to 1 electron-volt). For example, you can measure the universe length using Planck length units with (IIRC) 200 digits. You can mentally talk about 1/10 of a Planck length, but physically it has no sense.
    – SJuan76
    Feb 24, 2015 at 17:50
  • Don't you mean divide by 10000? Multiplying by 10000 would just make the assumption from the thread opener more likely to fail. Also maybe my device doesn't display the electron mass correctly but it should be 10^-31
    – Mike
    Feb 24, 2015 at 20:28
  • I do mean multiply by 10000. If you want to store 1.0001 as an integer, you need to multiply it by 10000 before storing it as 10001. I was using superscripts characters for the -31, maybe they don't show correctly on all browsers. Look fine in Firefox.
    – tcrosley
    Feb 24, 2015 at 21:01
  • @SJuan76 There's something called future-proofing. In 1850, we could talk about a unit of 10^-20 meters (a lot smaller than an atom, but still a lot bigger than a Planck length), but physically, doing so made no sense. Then people figured out the internal structure of an atom. Sure, quarks look fundamental, but all we can really say is (a) they act in ways consistent with how we expect fundamental particles to behave, and (b) we've not yet found a next turtle down. In 1850, we could say the same two things about atoms. If we do find a next turtle, units of 1/10 Planck become quite useful. Feb 24, 2015 at 22:30
  • It's a common misconception that space or time are quantized in Planck units! You can't represent the universe by a 4-dimensional array, at least not in the current theories... So fractions of Planck lengths are physically meaningful (but the results that come out of General Relativity and/or QM start blowing up or contradicting each other).
    – yatima2975
    Feb 25, 2015 at 12:37
5

First I would answer the question what physical values can/should be represented by an integer number?

Integer is a representation of a natural number (and differences between them) in a computer system, so applying it to anything else is wrong. Thus, invoking distances or other quantities that belong to continuous domain is not an argument. For such quantities there are real number representations. And you can always chose an arbirarily large unit and fit any value with a given precision.

So what are physical values that are natural numbers and can they overflow 64bit integer?

I can think of two. Number of physical objects (like atoms), and energy levels that a quantum system can be in. Those are two things that are strictly integer. Now, I know you can split an atom, but it still produces an integer amount and you cannot split it indefinitely. Both of those can easily surpass 64bit range of unsigned integer. Number of atoms is higher, and one atom can be in more than one energy state.

Whether information is physical or not, is very debatable. I would say it is not. Therefore, I wouldn't say amount of information is a physical thing. So is not the amount of RAM or anything like that. If you would allow this, then easily number of atoms surpasses this number, because you need more than one atom to store one bit with today's technology.

4
  • The set N of natural numbers includes only non-negative integers. I know what you meant, but "natural number" has a specific mathematical definition inconsistent with how you are using it.
    – user22815
    Feb 24, 2015 at 17:55
  • I am not really sure. Integer types do represent natural numbers (within a given range of course, which is implied). Is that not true? I think you assumed I implied equality between the sets. This is not true, any natural number can be represented by an integer. Please note that I also said differences between them. I didn't feel like getting into signed/unsigned was necessary. Singed type is only necessary when you deal with differences.
    – luk32
    Feb 24, 2015 at 20:47
  • While the physicality of the information stored is debatable, and a question for philosophers more than for physicists, the physicality of the mechanisms by which it is stored is quite certain. Therefore, while the applicability to a number of bits of information is questionable, the number of bits worth of RAM chips is not. Feb 24, 2015 at 23:03
  • @MatthewNajmon Of course, I agree, that's why I left the last sentence. The number of bits of a RAM chip will be lower than number of atoms for quite some time, so you can use the latter. In other words why use number of bits, when you can use number of atoms of the same RAM chip? Currently a bit of information is represented by a state that a physical system is in, so you could store more than one bit per atom, but it's far from application nowadays, and I still don't see how it can be more than number of quantum states of such system. But I totally agree with your premise.
    – luk32
    Feb 24, 2015 at 23:13
4

In addition to Jerry101's answer, I would like to offer this very simple and practical test for correctness:

Suppose you allocate some memory via malloc, in an 64-bit OS. Let's suppose the memory allocator decides to return to you a valid memory block, of the size you requested, but where the 63-th bit is set.

In other words, let's suppose there exists some programming environements where 0xFFFFFFFFxxxxxxxx are legitimate memory ranges that might be returned from a call to malloc.

The question is, will your code still work as intended?

When the analogous situation occurs to 32-bit operating systems, some software did not operate correctly if they are given memory addresses "in the upper half". Originally, such memory addresses were thought to be only available to the privileged code (operating systems, device drivers, and peripheral hardware), but because of the 32-bit address space crunch, OS vendors decided to make part of that reserved space available to applications that ask for it.

Fortunately, this situation is quite unlikely to happen for 64-bit programs for a while, at least not in a decade.

When that situation finally happens, it means that 128-bit addressable processors and operating systems would have become mainstream by that time, and that they would be able to provide a "64-bit emulation environment" to allow those "legacy applications" to operate under assumptions similar to today's 64-bit operating systems.

Finally, note that this discussion only focuses on memory addresses. A similar issue with timestamps must be taken with more precaution, because certain timestamp formats allocate a lot of bits of precision to the microseconds, and therefore leaves fewer bits available to represent time in the future. These issues are summarized in the Wikipedia article on Year 2038 problem.

4

This is a question you need to ask on a case-by-case basis. You should not be using a general assumption that 64-bit arithmetic will not overflow, because even when correct quantities will be in a much smaller range, a malicious data source could end up giving you unreasonable quantities which could overflow, and it's better to be prepared for this situation than to be hit by it unexpectedly.

There are some cases where it makes sense to write code that depends on non-overflow of 64-bit numbers. The main class of example I know is counters, where the counter is incremented each time it's used. Even at a rate of one increment per nanosecond (not practical) it would take more than a century to overflow.

Note that while it may at first seem "always wrong in principle" to rely on "time until failure" for the correctness of a system, we do this all the time with authentication/login. Given enough time (for brute forcing), any such system (whether based on passwords, private keys, session tokens, etc.) is broken.

2

Is it POSSIBLE for a physical quantity to not fit in 64 bits? Of course. Others have pointed out counting the number of atoms in the sun or the number of millimeters to the next galaxy. Whether such cases are relevant to your application depends on what your application is. If you're counting the number of items in any given bin in your warehouse, 16 bits would likely be sufficient. If you're compiling statistics about number of people in the world meeting various conditions, you need to be able to record billions, so you'll need more than 32 bits, at which point you'd presumably go to 64 (as few computers have built-in support for 37 bit numbers, etc). If this is a chemistry application that's counting moles worth of atoms, 64 bits will not be sufficient.

Technically, just because no computer today has 2^64 bytes of memory doesn't necessarily mean that an array index could never be more than 2^64. There's a concept called a "sparse array" where many of the elements of the array are not physically stored anywhere, and such unstored values are assumed to have some default value like null or zero. But I suppose that if you are writing a function to search an array or list of some kind, and the size of the field you are using to hold the index into the array is more than double the largest possible address, then checking for overflow when adding two indexes would not be strictly necessary.

1
  • Good point about sparse arrays. Additionally, even with an array that is fully populated, it is still entirely possible, albeit rather slow, and is in some cases quite necessary, to work with an array too large to fit the entirety of the array in RAM all at once. This is done simply by storing the whole thing in a slower but much larger medium, such as a HDD, and then pulling to RAM just the few elements you're working with at the moment. Even a small HDD is big enough to hold an array much larger than the OP is wanting to assume. Feb 24, 2015 at 23:09
0

It is unreasonable to assume a 64 bit integer can hold all numbers. Multiple reasons:

  1. The max and min 64 bit integer are finite numbers. For every finite number a larger and smaller finite number exists.

  2. Calculations with 128 bit and 256 bit numbers are currently used in various places. Many processors have specific instructions that operate on 128 bit integers.

  3. 20 years ago, a 1 GB disk was considered "large". Today a 1 TB disk is considered small. 20 years ago average desktops had about 16 MB RAM. My current desktop has more than 16 GB RAM. Harddisk space and RAM has grown exponentially in the past, and is predicted to grow exponentially in the future. Unless somebody can come up with a very good reason why it should stop growing, it doesn't make sense to assume it will stop.

Not the answer you're looking for? Browse other questions tagged or ask your own question.