Editing Big numbers
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 13: | Line 13: | ||
===Little-endian vs. big-endian=== | ===Little-endian vs. big-endian=== | ||
The ''byte'' is the fundamental addressable unit of memory for a given processor. This is distinct from the ''word'', which is the natural unit of data for a given processor. For example, the Intel 386 processor had 8 bits to a byte but 32 bits to a word. Each byte in memory may be addressed individually by a pointer, but one cannot address the individual bits in them. That being said, when a 32-bit machine word is written to memory, there are two ways it could be done. Suppose the number {{hex|CAFEBABE}} is stored at memory location {{hex|DEADBEEF}}. This will occupy four bytes of memory, and they must be contiguous so that the processor can read and write them as units. The important question is whether the most significant byte (in this case {{hex|CA}}) comes first (big-endian) or last (little-endian). The following table shows where each byte ends up in each scheme. | The ''byte'' is the fundamental addressable unit of memory for a given processor. This is distinct from the ''word'', which is the natural unit of data for a given processor. For example, the Intel 386 processor had 8 bits to a byte but 32 bits to a word. Each byte in memory may be addressed individually by a pointer, but one cannot address the individual bits in them. That being said, when a 32-bit machine word is written to memory, there are two ways it could be done. Suppose the number {{hex|CAFEBABE}} is stored at memory location {{hex|DEADBEEF}}. This will occupy four bytes of memory, and they must be contiguous so that the processor can read and write them as units. The important question is whether the most significant byte (in this case {{hex|CA}}) comes first (big-endian) or last (little-endian). The following table shows where each byte ends up in each scheme. | ||
− | + | {|style="border-collapse: collapse; border-width: 1px; border-style: solid; border-color: #000" | |
− | + | ! style="border-style: solid; border-width: 1px" | | |
− | + | ! style="border-style: solid; border-width: 1px" | {{hex|DEADBEEF}} | |
− | !| {{hex|DEADBEEF}} | + | ! style="border-style: solid; border-width: 1px" | {{hex|DEADBEF0}} |
− | !| {{hex|DEADBEF0}} | + | ! style="border-style: solid; border-width: 1px" | {{hex|DEADBEF1}} |
− | !| {{hex|DEADBEF1}} | + | ! style="border-style: solid; border-width: 1px" | {{hex|DEADBEF2}} |
− | !| {{hex|DEADBEF2}} | + | |
|- | |- | ||
− | || '''Big-endian''' | + | | style="border-style: solid; border-width: 1px" | '''Big-endian''' |
− | || {{hex|CA}} | + | | style="border-style: solid; border-width: 1px" | {{hex|CA}} |
− | || {{hex|FE}} | + | | style="border-style: solid; border-width: 1px" | {{hex|FE}} |
− | || {{hex|BA}} | + | | style="border-style: solid; border-width: 1px" | {{hex|BA}} |
− | || {{hex| | + | | style="border-style: solid; border-width: 1px" | {{hex|16}} |
|- | |- | ||
− | || '''Little-endian''' | + | | style="border-style: solid; border-width: 1px" | '''Little-endian''' |
− | || {{hex|BE}} | + | | style="border-style: solid; border-width: 1px" | {{hex|BE}} |
− | || {{hex|BA}} | + | | style="border-style: solid; border-width: 1px" | {{hex|BA}} |
− | || {{hex|FE}} | + | | style="border-style: solid; border-width: 1px" | {{hex|FE}} |
− | || {{hex|CA}} | + | | style="border-style: solid; border-width: 1px" | {{hex|CA}} |
|} | |} | ||
One faces a similar choice when storing bignums: does the most significant part get stored in the first or the last position of the array? Almost every processor is either consistently little-endian or consistently big-endian, but this does not affect the programmer's ability to choose either little-endian or big-endian representations for bignums as the application requires. The importance of this is discussed in the next section. | One faces a similar choice when storing bignums: does the most significant part get stored in the first or the last position of the array? Almost every processor is either consistently little-endian or consistently big-endian, but this does not affect the programmer's ability to choose either little-endian or big-endian representations for bignums as the application requires. The importance of this is discussed in the next section. | ||
Line 39: | Line 38: | ||
On the other hand, sometimes it is not so easy to determine in advance the size of the numbers we might be working with, or a problem might have bundled test cases and a strict time limit, forcing the programmer to make the small cases run more quickly than the large ones. When this occurs it is a better idea to use ''dynamic'' bignums, which can expand or shrink according to their length. Dynamic bignums are trickier to code than fixed-width ones: when we add them, for example, we have to take into account that they might not be of the same length; we might then treat all the missing digits as zeroes, but in any case it requires extra code. When using dynamic bignums the difference between the little-endian and big-endian representations becomes significant. If we store the bignums little-endian, and add them, alignment is free: just look at the first entry in each of them; they are in the ones' places of their respective numbers. The code presented in this article will assume the little-endian representation. | On the other hand, sometimes it is not so easy to determine in advance the size of the numbers we might be working with, or a problem might have bundled test cases and a strict time limit, forcing the programmer to make the small cases run more quickly than the large ones. When this occurs it is a better idea to use ''dynamic'' bignums, which can expand or shrink according to their length. Dynamic bignums are trickier to code than fixed-width ones: when we add them, for example, we have to take into account that they might not be of the same length; we might then treat all the missing digits as zeroes, but in any case it requires extra code. When using dynamic bignums the difference between the little-endian and big-endian representations becomes significant. If we store the bignums little-endian, and add them, alignment is free: just look at the first entry in each of them; they are in the ones' places of their respective numbers. The code presented in this article will assume the little-endian representation. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
===Error conditions=== | ===Error conditions=== | ||
Line 92: | Line 45: | ||
* Fixed-width bignums may overflow when adding or multiplying. You will be able to detect this because a carry is generated in the left-most column when adding, or something like that. Naively failing to check this may result in out-of-bounds array access. | * Fixed-width bignums may overflow when adding or multiplying. You will be able to detect this because a carry is generated in the left-most column when adding, or something like that. Naively failing to check this may result in out-of-bounds array access. | ||
* Check that the input does not overflow a fixed-width bignum. Naively failing to check this will probably result in an out-of-bounds array access. | * Check that the input does not overflow a fixed-width bignum. Naively failing to check this will probably result in an out-of-bounds array access. | ||
− | * If you're writing a bignum library, and intend to reuse the code, you might also want to check, with dynamic bignums, that your attempts to allocate more memory actually succeed. | + | * If you're writing a bignum library, and intend to reuse the code, you might also want to check, with dynamic bignums, that your attempts to allocate more memory actually succeed. If not, and you just keep going on anyway, a segfault is almost certain to occur. If you do check, you can throw an exception. |
<!-- | <!-- | ||
Line 114: | Line 67: | ||
The other method is suitable only for fixed-size bignums and is based on the ''two's complement'' convention used in almost all modern processors for built-in integer types. We suppose that the radix is <math>b</math> and that the bignum contains <math>n</math> digits. Then, the largest positive integer we can represent is <math>b^w-1</math>. Notice that when | The other method is suitable only for fixed-size bignums and is based on the ''two's complement'' convention used in almost all modern processors for built-in integer types. We suppose that the radix is <math>b</math> and that the bignum contains <math>n</math> digits. Then, the largest positive integer we can represent is <math>b^w-1</math>. Notice that when | ||
--> | --> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |