How can one scale an Int64 value without access to a larger type?

Question

I refactored the code in this class to be in a form that is more friendly to my use cases; one issue that I noticed during testing is that I cannot convert this particular equation to use long inputs because assigning to the a and m variables overflow on the multiplication/subtraction steps. Everything is just peachy when using int inputs because they can be casted to a long to prevent overflow. Is there anything one can do to get the proper behavior when the inputs are long?*

public static Func<int, int> Scale(int inputX, int inputY, int outputX, int outputY) {
    if (inputX > inputY) {
        var z = inputX;

        inputX = inputY;
        inputY = z;
    }

    if (outputX > outputY) {
        var z = outputX;

        outputX = outputY;
        outputY = z;
    }

    var a = (((((double)inputScaleX) * (outputScaleX - outputScaleY)) / ((long)inputScaleY - inputScaleX)) + outputScaleX);
    var m = (((double)(outputScaleY - outputScaleX)) / ((long)inputScaleY - inputScaleX));

    return (value) => ((int)((value * m) + a));
}

For example, if I replaced every instance of int in the function above with long then result will have an incorrect value in the following code:

Func<long, long> scaler = Scale(long.MinValue, long.MaxValue, -5, 5);

var result = scaler(long.MaxValue - 3);

The expected result is 4 but the actual result of -9223372036854775808 is not only wrong, it ends up being way outside the defined range of [-5, 5].

*Other than straight up using BigInt or implementing 64-bit multiplication and division in software; I am already implementing these operations as workaround and am looking for alternative solutions that I haven't yet come across.

@ChristopherSchultz I'd honestly accept answers in any language but those two overlap so much that I figured I'd include Java explicitly; converting the function to it would require absolutely minimal changes. — Kittoes0124, Nov 21 '19 at 17:05
@CarlosHeuberger The exact string used to define a 64 bit integer - signed or unsigned - is pretty irrelevant. But luckily it does have a BigInt too: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html — Christopher, Nov 21 '19 at 17:07
@CarlosHeuberger: The question was about "what can I do if none of the buildin numeric types are large enough?". BigInteger is the answer. — Christopher, Nov 21 '19 at 17:19
@Christopher It strictly is not about using larger numeric types as I have artificially constrained myself to 64-bit integers; I already have a solution that involves multiplication/division using a software-based Int128 and am looking for possible alternatives (assuming they exist). — Kittoes0124, Nov 21 '19 at 17:38
Where in the above code do you think the type "gets promoted to `long`"? Ints do not get automatically promoted to long; they overflow instead. But sometimes the overflow behaviour gives you what you want. — DodgyCodeException, Nov 21 '19 at 17:43
@DodgyCodeException My explanation here is technically inaccurate as the `int` gets promoted to a `double` (I have a strictly integer version that suffers from the same exact issue); in either case the wider type is readily available and has enough room to perform the maths properly. Bump the input width up to 64 bits and such magic no longer is possible. — Kittoes0124, Nov 21 '19 at 17:45
Are you asking about *how* classes like `BitInt`(.NET)/`BigInteger`(Java) perform their magic? Well... I suppose you could just look at the code for those classes. — Christopher Schultz, Nov 22 '19 at 16:57
@ChristopherSchultz Not really, I have explored those and could just use them and am trying to figure out how I can do this without resorting to something so heavy-handed. The obvious solution is 128-bit operations, as I've already stated I'm working on, but I am curious about possible (but seemingly unlikely) solutions that aren't so obvious. — Kittoes0124, Nov 22 '19 at 21:25
Aha, so it's fair to say that you are only interested in a specific use-case (the one presented in your question) which means that you really only care about being able to work with numbers that can't fit in the fixed-precision integral types the language offers directly. You could look at [this answer](https://stackoverflow.com/a/28258429/276232) for .NET which has a reference to a third-party .NET library which provides specifically a `uint_128` data type if you think that `BigInt` is overkill. You also might be able to simplify your algorithm to limit possible overflow. — Christopher Schultz, Nov 25 '19 at 23:16

Christopher · Answer 1 · 2019-11-21T17:05:03.763

If you have to do math and none of the buildin .NET Integer types is long/large enough, BigInt is the droid you are looking for.

As long as you do not run out of memory, it can take a number of arbitrary size. Do however note that the performance is very bad, as should be expected. After all, Arbtitrary size does not come without tradeoffs. And unlike any other Numeric type, it can grow big.

Looking at the source code, it seems to be little more then a List<uint> with a int for the sign. Unfortunately that designs makes it vulnerable to Fragmentation based OutOfMemory exceptions and related List<uint> growth issues. I was hoping it would use a Linked List internally, but no such luck.

Java has a equivalent type (I asume all higher languages do), but I have no data on it's workings.

While I don't particularly care about performance of the delegate generation step, I am trying to learn if there is some other method that I'm not yet privy to. — Kittoes0124, Nov 21 '19 at 17:01

How can one scale an Int64 value without access to a larger type?

1 Answers1