There are a lot of similar questions asked on SO, but I've yet to find one that works and is easily portable to C#. Most involve C++ or similar, and the (presumably) working answers rely on either embedded assembly or native C/C++ functions that don't exist in C#. Several functions work for part of the range, but fail at other parts. I found one working answer I was able to port to C#, but it was very slow (turns out it's decently-fast when I compile to x64 instead of x86, so I posted it as the answer to beat).
In my case, I have a random 64-bit Int64/UInt64 (using the xoshiro256p algorithm, though that's likely irrelevant). I want to scale that number to any arbitrary range in the type's allowed values. For example, I might want to scale Int64 to the range [1000, 35000]. This is, conceptually, easy enough:
UInt64 minVal = 1000;
UInt64 maxVal = 35000;
UInt64 maxInt = UInt64.MaxValue;
UInt64 randInt = NextUInt64(); // Random value between 0 and maxInt.
UInt64 diff = maxVal - minVal + 1;
UInt64 scaledInt = randInt * diff / maxInt; // This line can overflow.
return scaledInt + minVal;
As noted by many other people, and the comment above, the problem is that randInt * diff can potentially overflow.
On paper, I could simply store that intermediate result in a 128-bit integer, then store the result of the division in the 64-bit output. But 128-bit math isn't native to 64-bit systems, and I'd rather avoid arbitrary-precision libraries since I'll be making lots of calls to this function and efficiency will be notable.
I could multiply by a double to get 53 bits of precision, which is fine for what I'm currently doing, but I'd rather come up with a proper solution.
I could create a C++ library with one of the ASM solutions and call that library, but I'd like something that's pure C#.
randInt * diff / maxInt is in the range [0, maxInt] (and each value itself is in the same range).I've tested the following solutions for relative performance. Each test ran 1 million iterations of my random number generator, scaling using various methods. I started by generating random numbers and putting them in lists (one for signed, one for unsigned). Then I ran through each list and scaled it into a second list.
I initially had a bunch of tests in debug mode. It mostly didn't matter (we're testing relative performance), but the Int128/UInt128 libraries fared much better in release mode.
Numbers in parenthesis are the debug time. I include them here because I still want decent performance while debugging. The Int128 library, for example, is great for release mode, but terrible for debug. It might be useful to use something that has a better balance until you're ready for final release. Because I'm testing a million samples, the time in milliseconds is also the time in nanoseconds per operation (all million UInt64s get generated in 33 ms, so each one is generated in 33 ns).
Source code for my testing can be found here, on GitGub.
I couldn't get these to give proper results.
Most accurate way to do a combined multiply-and-divide operation in 64-bit?
How can I descale x by n/d, when x*n overflows?
Fast method to multiply integer by proper fraction without floats or overflow
(a * b) / c MulDiv and dealing with overflow from intermediate multiplication
How to multiply a 64 bit integer by a fraction in C++ while minimizing error?
But 128-bit math isn't native to 64-bit systems
While that is mostly true, there is a decent way to get the full 128-bit product of two 64-bit integers: Math.BigMul (for .NET 5 and later)
x64 has a corresponding division with a 128-bit input, and such a pair of full-multiply followed by a wide-division would implement this "scale integer by a proper fraction" operation (with the limitation that the fraction must not be greater than 1, otherwise an overflow could result). However, C# doesn't have access to wide division, and even if it did, it wouldn't be very efficient on most hardware.
But you can just use BigMul directly too, because the divisor should really be 264 to begin with (not 264 - 1), and BigMul automatically divides by 264.
So the code becomes: (not tested)
ulong ignore;
ulong scaled = Math.BigMul(randInt, diff, out ignore);
return scaled + minVal;
For older versions of .NET, getting the high 64 bits of the product could be done like this:
static ulong High64BitsOfProduct(ulong a, ulong b)
{
// decompose into 32bit blocks (in ulong to avoid casts later)
ulong al = (uint)a;
ulong ah = a >> 32;
ulong bl = (uint)b;
ulong bh = b >> 32;
// low times low and high times high
ulong l = al * bl;
ulong h = ah * bh;
// cross terms
ulong x1 = al * bh;
ulong x2 = ah * bl;
// carry from low half of product into high half
ulong carry = ((l >> 32) + (uint)x1 + (uint)x2) >> 32;
// add up all the parts
return h + (x1 >> 32) + (x2 >> 32) + carry;
}
Unfortunately that's not as good as Math.BigMul, but at least there is still no division.