Category talk:Wren-long: Difference between revisions
→64-bit integer arithmetic: Revised preamble following introduction of Long class.
(→Source code: Added support for signed 64 bit arithmetic (Long class).) |
(→64-bit integer arithmetic: Revised preamble following introduction of Long class.) |
||
Line 7:
However, some tasks on RC only require integers within the 64-bit range and ''BigInt'' feels like overkill for such tasks.
This module aims to remedy that situation by providing
====ULong====
Internally, a 64-bit unsigned integer is represented by two unsigned 32-bit integral ''Num''s, a low and a high part, though this is generally invisible to the user.
The design of ''ULong'' follows closely that of the ''BigInt'' class though the implementation is generally much simpler and hopefully more performant for numbers within its range.
Line 28 ⟶ 30:
The most obvious way to perform division of larger numbers is to first obtain an estimate of the result by treating them as ''Num''s and then refine this result iteratively until the exact result is obtained. However, this is easier said than done because the accuracy of the initial estimate will depend on the magnitude of the numbers and one has to guard against overflow when performing the iterations. Consequently, this is quite a ''slow'' operation.
====Long====
Internally, a 64-bit signed integer is represented by a ULong (its ''magnitude'') and a sign (-1 for negative, 0 for zero and +1 for positive integers). This design has the following advantages:
1. Longs have double the range of ULongs and not one bit less as is usually the case for 64-bit signed integers where one bit is needed to represent the sign.
2. Apart from manipulation of the sign, most of the methods for the Long type can simply defer to the corresponding methods for the ULong type which makes the code for the Long class much shorter and simpler than it otherwise would have been.
3. There is no need to support bitwise operations and other stuff which is only really relevant to unsigned integers such as prime number routines. This again shortens and simplifies the code.
4. It is relatively easy to mix both Longs and ULongs in arithmetic expressions by performing the necessary conversions automatically.
However, a big disadvantage is that Longs use 50% more memory (3 Nums instead of two) and are slightly slower than ULongs which means that the latter should normally be preferred unless you know or suspect that you will need to deal with negative numbers.
A peculiarity of the design (though not necessarily a disadvantage) is that an overflow wraps around to zero rather than the opposite end of the range as is usual for 64-bit signed integers.
===Source code===
| |||