2. Видимо, первая, т.к. нет вызовов функций - просто работа с битами.
3. Модифицируя пример выше как-то так:
binary_to_double(< F.
Там точно две правые скобки перед закрывающей обычной не нужны?
4. printf по умолчанию выводит с точностью 6 десятичных знаков с округлением.
5. а) при умножении на 0 результат тоже 0, если только это не бесконечность (тогда NaN). Также отдельно обрабатываем ситуацию с + и - бесконечностью и NaN'ом. б) иначе, первый бит xor'им в) экспоненты складываем и вычитаем 254 г) мантиссам дописываем единицу на место последнего бита экспоненты (биты знака и экспоненты, понятно, обнуляем), умножаем с 64-х битным результатом, определяем положение старшего бита и в зависимости от него сдвигаем вправо на нужное число разрядов, затем отбрасываем старший разряд и зануляем старший значимый бит д) сохраняем результат в 32-х битное целое
6. а) отдельно обрабатываем ситуацию с бесконечностями и NaN'ами. б) определяем число с большей экспонентой, при равенстве экспонент - с большей мантиссой. Далее считаем, что это первое число, а оставшееся - второе. Результат точно будет иметь знак первого числа. в) сдвигаем на один разряд вправо мантиссу каждого числа, дописываем в нужное место единичку. Запоминаем, что экспоненту результата нужно будет изменить на 2. г) в зависимости от разности экспонент сдвигаем мантиссу на нужное число бит вправо (денормализуем). Тут нужно помнить, что сдвигать на 32 бита и более нельзя, нужно просто считать, что мантисса второго числа 0. д) в зависимости от того, совпадают знаки чисел или нет, складываем или вычитаем числа. Альтернатива: Можно всегда складывать, предварительно обратив и прибавив единицу к мантиссам отрицательных чисел. В последнем случае знак результата - это знак результата сложения, а отрицательный результат сложения нужно ещё раз обратить и прибавить единицу. Вроде первый вариант быстрее. е) определяем, где находится старший бит и сдвигаем на нужное число битов вправо или влево. Отдельно обрабатываем 0 в результате. Запоминаем сдвиг как коррекцию экспоненты. ж) вычисляем экспоненту результата как экспоненту первого числа и учитываем коррекцию. Если вдруг получили переполнение (экспоненту больше разрешённой), то возвращаем одну из бесконечностей. з) сохраняем число как в пункте 5.
7*. Напишите функцию получения обратного заданному float'у, пользуясь только целочисленными операциями и, возможно, каким-то количеством вспомогательных данных.
1. добавить слева один бит и разделить на 2^23 для float или на 2^52 для double ;)
2. почти. основная проблема второй функции - math:pow работает с float. ее необходимо оптимизировать, заменив math:pow на битовые сдвиги.
3. так то да :) но хотелось увидеть алгоритм из binary_to_float1
закрывающие скобки нужны. + за внимательность :)
4. bingo!
5. а) я специально опустил специальные случаи (0 и +/-infinity), чтобы не перегружать пост в) не понял почему 254, по-моему 127. г) если после перемножения полученное число больше 2^46 - добавить к экспоненте 1 и вычесть из результата перемножения 2^46.
6. а) см 5а в) нет необходимости сдвигать вправо, надо ли будет менять экспоненту лучше определять по результатам сложения мантисс, как в 5г. д) первый вариант имеет еще одно преимущество - мы всегда работаем с unsigned. Во втором варианте всегда должно получаться положительное число, см пукт б е) см 5г. и влево сдвигать точно не надо.
7. я не могу придумать алгоритм обращения мантиссы - не хватает математики :(
5в. да, мой косяк. 6е. хмм, 1+(-1/2), результат придётся сдвинуть на 1 _влево_ и учесть сдвиг в экспоненте. 7. Вот этот ряд быстро сходится к нужному числу: X' = X * (1 + (1 - A*X) + (1 - A*X)^2), где X - начальное приближение или значение на предыдущем шаге, A - значение, к которому требуется посчитать обратное. A > 1, A < 2, X < 1, X > 0. Обратное к 1 получается 0.(9), что то же самое. Если в качестве начального приближения выбрать таблицу, в которой 16 бит будут верными (порядка 120 КиБ доп. данных), то алгоритм сходится за одну итерацию. С одним начальным приближением потребуется 2 или 3. Ну и там всякая пляска для с тем, что мы считаем число 2^32*X', не учитываем значимую единицу и всякое такое. Если интересно, могу кинуть полную реализацию.
Хмм, я ступил, это для фиксированной точки только в таком варианте канает, а для float несколько сложнее - не знаешь заранее, когда нужно остановиться, т.е. число итераций не фиксированное, и нужно учитывать текущую коррекцию. Ряд-то всё равно правильный, но реализация сложнее. Пожалуй, её предоставить сходу не смогу :)
7. Ты можешь представить число как 1.(0...0)(32 значащих бита) и начальное приближение как 1/2=0.(10...0). А дальше учесть, что при вычислении на очередном шаге тебе нужно получать результат, умноженный на 2^n (т.е. биты дробной части). Также нужно отслеживать текущую точность и текущее количество полученных значимых бит. Потому и написал, что для числа с фиксированной точкой проще: заранее знаем число итераций и вычисление просто превращается в простую формулу (несколько последовательных вычислений формулы).
По теме.
0. Косячник.
1. Дописать единичку слева, остальное - дробная часть.
2. Видимо, первая, т.к. нет вызовов функций - просто работа с битами.
3. Модифицируя пример выше как-то так:
binary_to_double(<
F.
Там точно две правые скобки перед закрывающей обычной не нужны?
4. printf по умолчанию выводит с точностью 6 десятичных знаков с округлением.
5.
а) при умножении на 0 результат тоже 0, если только это не бесконечность (тогда NaN). Также отдельно обрабатываем ситуацию с + и - бесконечностью и NaN'ом.
б) иначе, первый бит xor'им
в) экспоненты складываем и вычитаем 254
г) мантиссам дописываем единицу на место последнего бита экспоненты (биты знака и экспоненты, понятно, обнуляем), умножаем с 64-х битным результатом, определяем положение старшего бита и в зависимости от него сдвигаем вправо на нужное число разрядов, затем отбрасываем старший разряд и зануляем старший значимый бит
д) сохраняем результат в 32-х битное целое
6.
а) отдельно обрабатываем ситуацию с бесконечностями и NaN'ами.
б) определяем число с большей экспонентой, при равенстве экспонент - с большей мантиссой. Далее считаем, что это первое число, а оставшееся - второе. Результат точно будет иметь знак первого числа.
в) сдвигаем на один разряд вправо мантиссу каждого числа, дописываем в нужное место единичку. Запоминаем, что экспоненту результата нужно будет изменить на 2.
г) в зависимости от разности экспонент сдвигаем мантиссу на нужное число бит вправо (денормализуем). Тут нужно помнить, что сдвигать на 32 бита и более нельзя, нужно просто считать, что мантисса второго числа 0.
д) в зависимости от того, совпадают знаки чисел или нет, складываем или вычитаем числа.
Альтернатива: Можно всегда складывать, предварительно обратив и прибавив единицу к мантиссам отрицательных чисел. В последнем случае знак результата - это знак результата сложения, а отрицательный результат сложения нужно ещё раз обратить и прибавить единицу. Вроде первый вариант быстрее.
е) определяем, где находится старший бит и сдвигаем на нужное число битов вправо или влево. Отдельно обрабатываем 0 в результате. Запоминаем сдвиг как коррекцию экспоненты.
ж) вычисляем экспоненту результата как экспоненту первого числа и учитываем коррекцию. Если вдруг получили переполнение (экспоненту больше разрешённой), то возвращаем одну из бесконечностей.
з) сохраняем число как в пункте 5.
7*. Напишите функцию получения обратного заданному float'у, пользуясь только целочисленными операциями и, возможно, каким-то количеством вспомогательных данных.
Reply
2. почти. основная проблема второй функции - math:pow работает с float.
ее необходимо оптимизировать, заменив math:pow на битовые сдвиги.
3. так то да :) но хотелось увидеть алгоритм из binary_to_float1
закрывающие скобки нужны. + за внимательность :)
4. bingo!
5.
а) я специально опустил специальные случаи (0 и +/-infinity), чтобы не перегружать пост
в) не понял почему 254, по-моему 127.
г) если после перемножения полученное число больше 2^46 - добавить к экспоненте 1 и вычесть из результата перемножения 2^46.
6.
а) см 5а
в) нет необходимости сдвигать вправо, надо ли будет менять экспоненту лучше определять по результатам сложения мантисс, как в 5г.
д) первый вариант имеет еще одно преимущество - мы всегда работаем с unsigned. Во втором варианте всегда должно получаться положительное число, см пукт б
е) см 5г. и влево сдвигать точно не надо.
7. я не могу придумать алгоритм обращения мантиссы - не хватает математики :(
Reply
6е. хмм, 1+(-1/2), результат придётся сдвинуть на 1 _влево_ и учесть сдвиг в экспоненте.
7. Вот этот ряд быстро сходится к нужному числу:
X' = X * (1 + (1 - A*X) + (1 - A*X)^2), где X - начальное приближение или значение на предыдущем шаге, A - значение, к которому требуется посчитать обратное. A > 1, A < 2, X < 1, X > 0. Обратное к 1 получается 0.(9), что то же самое. Если в качестве начального приближения выбрать таблицу, в которой 16 бит будут верными (порядка 120 КиБ доп. данных), то алгоритм сходится за одну итерацию. С одним начальным приближением потребуется 2 или 3. Ну и там всякая пляска для с тем, что мы считаем число 2^32*X', не учитываем значимую единицу и всякое такое. Если интересно, могу кинуть полную реализацию.
Reply
Reply
7. все равно ничего не понял. оригинальный алгоритм расчета мантиссы оперирует битами...
Reply
Потому и написал, что для числа с фиксированной точкой проще: заранее знаем число итераций и вычисление просто превращается в простую формулу (несколько последовательных вычислений формулы).
Reply
Leave a comment