Генерация случайного 128-битного десятичного числа в заданном диапазоне в go

Question

Допустим, у нас есть генератор случайных чисел, который может генерировать случайные 32- или 64-битные целые числа (например, rand.Rand в стандартной библиотеке)

Генерация случайного int64 в заданном диапазон [a,b] довольно прост:

rand.Seed(time.Now().UnixNano())
n := rand.Int63n(b-a) + a

Возможно ли сгенерировать случайный 128-битный десятичный знак (как определено в спецификации IEEE 754-2008) в заданном диапазоне из комбинации 32- или 64-битных случайных чисел

Answer 1

Это зависит от того, сколько значений вы хотите сгенерировать. Если достаточно, чтобы в указанном диапазоне не было больше 10 ^ 34 значений - это довольно просто.

Как я вижу проблему, случайное значение в диапазоне min..max можно вычислить как случайное (0. .1) * (max-min) + min

Похоже, нам нужно генерировать только десятичное значение 128 в диапазоне 0..1. Так что это случайное значение в диапазоне 0..10 ^ 34-1 с показателем степени -34. Это значение может быть сгенерировано с помощью стандартного случайного пакета golang.

Для умножения, добавления и подстановки значений float128 можно использовать golang математический / большой пакет с нормализацией значений.

Answer 2

Возможно, но далеко не просто. Вот набросок решения, которое могло бы быть приемлемым - написание и отладка его, вероятно, потребует как минимум дня согласованных усилий.

Пусть min и max будут примитив. Декабрь128 объекты из go .mongodb.org / mon go -driver / bson. Пусть MAXBITS будет кратно 32; 128, вероятно, будет достаточным.

1. Получите значение (как большое.Инт) и показатель степени (как целое) min и max, используя метод BigInt.

2. Совместите мин и макс так, чтобы они имели одинаковый показатель степени. Насколько это возможно, выровняйте по левому краю значение с большим показателем, уменьшив его показатель и добавив соответствующее число нулей к правой стороне его значения. Если это приведет к тому, что абсолютное значение значимости станет> = 2**(MAXBITS-1), то либо

   • (а) сместите вправо значение с меньшим показателем, опустив цифры с правой стороны его Значение и увеличение его показателя приводит к потере точности.
   • (b) Динамически увеличивать MAXBITS.
   • (c) Бросить ошибку.

3. В этот момент оба показателя будут одинаковыми, и оба значения будут выровнены большими целыми числами. Отложите показатели пока, и пусть range (новый big.Int) будет maxSignificand - minSignificand. Это будет от 0 до 2**MAXBITS.

4. Превратите range в MAXBITS/32 uint32 с, используя методы Bytes или DivMod, что проще.

5. Если старшее слово range равно math.MaxUint32, тогда установите флаг limit на false, в противном случае true.

6. Для n от 0 до MAXBITS/32:

   • , если limit истинно, используйте rand.Int63n (!, , а не rand.Int31n или rand.Uint32 ), чтобы сгенерировать значение от 0 до n-го слова range включительно, привести его к uint32 и сохранить его в качестве n-го слова выходных данных. Если сгенерированное значение равно n-му слову range (т. Е. Если мы сгенерировали максимально возможное случайное значение для этого слова), то пусть limit останется истинным, в противном случае установите его на ложное.
   • Если limit ложно, используйте rand.Uint32, чтобы сгенерировать n-е слово для вывода. limit остается ложным независимо от сгенерированного значения.

7. Объедините сгенерированные слова в big.Int, построив []byte и используя big/Int.SetBytes или умножение и сложение , как удобно.

8. Добавьте сгенерированное значение к minSignificand, чтобы получить значение и результат.

9. Используйте ParseDecimal128FromBigInt с значение результата и показатель степени из шагов 2-3 для получения результата.

Сердцем алгоритма является шаг 6, который генерирует равномерное случайное целое число без знака произвольной длины 32 бита при время. Выравнивание на шаге 2 уменьшает проблему с плавающей запятой до целой, а вычитание на шаге 3 уменьшает ее до unsigned , так что нам нужно думать только об одной границе вместо 2 Флаг limit записывает, имеем ли мы дело с этой границей или уже сузили результат до интервала, который его не включает.

Предостережения:

1. Я не написал это, не говоря уже о том, чтобы проверить это. Возможно, я понял это неправильно. Приветствуется проверка работоспособности того, кто выполняет больше численных вычислений, чем я.
2. Генерация чисел в большом динамическом диапазоне c (включая пересечение нуля) потеряет некоторую точность и пропустит некоторые возможные выходные значения с меньшим экспоненты, если не используется смехотворно большой MAXBITS; однако 128 битов должны давать результат, по крайней мере, такой же хороший, как наивный алгоритм, реализованный в виде десятичной дроби128.
3. Производительность, вероятно, довольно плохая.

Answer 3

Go имеет пакет большого числа, который может делать произвольные целые числа длины: https://golang.org/pkg/math/big/

Он имеет генератор псевдослучайных чисел https://golang.org/pkg/math/big/#Int .Rand и криптопакет также имеет https://golang.org/pkg/crypto/rand/#Int

Вы можете указать максимальное значение, используя https://golang.org/pkg/math/big/#Int .Exp как 2^128.

Не могу говорить о производительности, или о том, соответствует ли это стандарту IEEE, но возможны большие случайные числа, такие как то, что вы использовали бы для UUID.

Answer 4

Возможно, но решение далеко не тривиально. Для правильного решения необходимо учитывать несколько моментов.

С одной стороны, значения с показателем E в 10 раз более вероятны, чем значения с показателем E - 1.

субнормальные числа и диапазоны, которые охватывают ноль.

Мне известна библиотека Rademacher с плавающей запятой , которая решила эту проблему для двоичных чисел с плавающей запятой, но Решение там сложное, и его автор еще не написал, как работает его алгоритм.

Answer 5

Это определенно то, что вы ищете.