Введение
Следующее доказательство длиннее, чем я хочу, но этот вопрос несколько дней не получен, и он заслуживает ответа.
Прежде чем перейти к доказательству, позвольте мне рассмотреть это интуитивно. Если мы определим по модулю возвращаемый результат для x % y , который находится в [- y / 2, + y / 2] (для положительных значений y ), тогда результат всегда либо x , либо уменьшается путем добавления (положительного или отрицательного) кратных y . Если результат равен x , он представим, поскольку x задан в представительной форме. Если результат уменьшается, то он обязательно кратен значению позиции младшего разряда в y , а его позиция наибольшего разряда не больше позиции самого большого разряда в y и, следовательно, он соответствует формату с плавающей запятой и представим.
С другой стороны, если мы определим по модулю возвращаемый результат для x % y , который находится в [0, y ), то небольшое отрицательное значение x должно быть увеличено путем добавления y . Когда x мало, он может иметь цифры в более низких позициях, чем y , и, если это так, результат добавления y должен иметь ненулевое значение цифра в самой низкой позиции, которую x делает, но она также должна иметь ненулевую цифру в более высокой позиции, чем маленькая x (потому что y добавление цифры в более высокое положение). Следовательно, результат должен содержать больше цифр, чем умещается в формате с плавающей запятой, и результат не может быть представлен.
Простой пример: -2 -60 % 1. Математический результат: 1-2 -60 , но это не может быть представлено только 53 битами в значении; ему нужны биты со значениями позиции от 2 -1 до 2 −60 , что требует 60 бит.
Точное симметричное по модулю
Во-первых, давайте посмотрим, что симметричное по модулю определено так, что x % y находится в [- y / 2, + y / 2] для положительного значения y всегда имеет представимый результат. Я также предполагаю, что x положительно, но аргументы для отрицательного x и / или отрицательного y симметричны, а результаты для x = 0 тривиальны.
x % y определяется как r таким, что r = x - q • y для некоторого целого числа q , и обычно мы определяем некоторые ограничения на r или q , так что r определяется однозначно (или, по крайней мере, обычно однозначно определяется с некоторой гибкостью, когда результат находится в конечной точке некоторого интервала). Поскольку q является целым числом, если оба значения x и y являются целыми числами, кратными некоторому числу g (которое может быть или не быть целое число), то r также является целым кратным g .
В формате с плавающей запятой число представляется с использованием знака, основания b (которое является целым числом больше 1), фиксированного числа p от основания. b цифр и показатель степени e . Представленное число составляет ± цифры × b e . Запишем отдельные цифры как d p -1 d p -2 * +1151 * д * +1152 ** ** 1154 тысячу сто пятьдесят три * р -3 ... д * ** 1 158 +1159 * 2 д 1 д 0 .
Рассмотрим входные данные x и y . Использование x i для обозначения базовых цифр b , используемых для представления x и e x для показателя степени, используемого для представления x , и аналогично для y , мы имеем x = x p -1 … x 0 × b e x и y = y p −1 … y 0 × b e y .
Обратите внимание, что x и y кратны меньшему из b e x и b e y и т. д. r должно быть тоже.
Если b e y ≤ b e x , тогда r кратно b e у . Кроме того, | r | обязательно меньше y . Это означает, что мы можем представить r как ± r p −1 … r 0 × b e y - r достаточно мало, чтобы эти цифры с показатель e y достаточно велик, чтобы представить его значение, и, поскольку он кратен b e y , ему не нужны цифры с меньшим показателем степени. Таким образом, r представимо в формате с плавающей запятой.
Теперь рассмотрим b e x <<em> b е у . Также предположим, что y нормализовано, что означает, что его начальная цифра, y p -1 , не равна нулю. (Если оно равно нулю, найдите нормализованное представление y , уменьшив его показатель степени, чтобы сместить ненулевую цифру в начальную позицию. Тогда применяется приведенный выше абзац. Если y не имеет ненулевые цифры, это ноль, и x % y не определено.) Тогда x <<em> y . В этом случае r равно либо x , либо x - y , потому что один из этих двух находится в [- y / 2, + y / 2]. Если r равно x , то оно представимо, поскольку x представимо. Если r равно x - y , то x ≥ ½ y и | r | ≤ x . Поскольку r кратно b e x и | г | <<em> x , мы должны быть в состоянии представить r как ± r p −1 … r 0 × b e x .
Асимметричный модуль может быть неточным
Приведенное выше доказательство говорит нам, что симметричное по модулю является точным, потому что результат всегда либо неизменен x , либо x уменьшен по величине настолько, что все необходимые цифры помещаются в плавающую формат точки. И это говорит нам, как разбить определенное по модулю так, что x % y находится в [0, y ): выберите x , который должно быть увеличено по величине.
У нас есть у = у p -1 … y 0 × b e у .Пусть y нормализуется, как описано выше.Для x выберите любое отрицательное значение, имеющее e x <<em> e y и не кратно b e y (имеется в видучто хотя бы одна из его цифр от x e y −1− e x до x 0 не равно нулю).В некоторых случаях, когда начальная цифра y равна 1, и заимствование у нее происходит, результат может быть представимым.В противном случае, наибольшая нужная ему цифра совпадает с самой большой цифрой y , и ей нужны цифры ниже b e y , и, следовательно, он не может быть представлен.