|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
07.06.2013, 12:17 | #1 |
Пользователь
Регистрация: 26.02.2013
Сообщений: 12
|
Алгоритм перевода чисел до 9999 в строку
В глубинах сети обнаружил этот алгоритм:
В начале eax содержит переводимое в строку положительное число. edx содержит довольно странное округление (2^32)/1000! 2^32 = 4294967296 т.е. если округлять правильно, то будет 4294967, а с этим числом уже не работает. Хотелось бы спросить, у уважаемых людей, как расширить его (алгоритм) на числа больше чем 10 000? PHP код:
|
07.06.2013, 12:34 | #2 |
C/C++, Asm
Участник клуба
Регистрация: 02.03.2010
Сообщений: 1,323
|
когда-то для MASM написал такое:
Код:
Код:
|
07.06.2013, 12:42 | #3 |
Пользователь
Регистрация: 26.02.2013
Сообщений: 12
|
Красота алгоритма, который я привел в том, что там нет деления))
И есть магия чисел |
07.06.2013, 14:10 | #4 |
Пользователь
Регистрация: 26.02.2013
Сообщений: 12
|
Наверняка есть какая нибудь математика, под это все, т.к. вот алгоритм перевода чисел в ASCII строки до 100 миллионов! (этот я не проверял)
Как же они находят критерии для округления множителей 2^32 и 2^45 ???!!! PHP код:
|
07.06.2013, 14:48 | #5 |
C/C++, Asm
Участник клуба
Регистрация: 02.03.2010
Сообщений: 1,323
|
если честно, то я вообще не понимаю зачем над числом меньшим 10^18 проводить какие-либо арифметические операции для того чтобы сконвертировать его в строку если есть такая шикарная инструкция как FBSTP
|
07.06.2013, 16:55 | #6 |
C/C++, Asm
Участник клуба
Регистрация: 02.03.2010
Сообщений: 1,323
|
в целом, если говорить про алгоритм, то если поискать, окажется, что основан на следующей идее
цифра[i] = int(10*frac(число*0.1^i)) // i>0 ну, и чтобы работать не с плавающей точкой, а с целыми, вместо факторов 0.1^i используются факторы фактор[i] = int(ceil((2^32 * 0.1^i) * 2^сдвиг[i])) сдвиг[i] = int(log2(10^i)) итог: цифра[i] = (10*(((число * фактор[i]) >> сдвиг[i]) & 0xFFFFFFFF)) >> 32; Последний раз редактировалось f.hump; 07.06.2013 в 17:01. |
08.06.2013, 14:48 | #7 |
Участник клуба
Регистрация: 11.01.2010
Сообщений: 1,139
|
Avizpr
в той же "глубине, где ты нарыл" этот алгоритм есть топик magic numbers -- почитай его внимательно А это "теоретическая часть" Деление на константу можно сделать на обратное число. Чтобы произвести беззнаковое целочисленное деление q = x / d, вам вначале нужно посчитать число, обратное делителю, f = 2r / d, где r определяет позицию двоично-десятичной точки (точка основания системы счисления). Затем нужно умножить x на f и сдвинуть полученный результат на r позиций вправо. Максимальное значение r равно 32+b, где b равно числу двоичных цифр в d минус 1. (b - это самое большое целое число, для которого 2b <= d). Используйте r = 32+b, чтобы покрыть максимальное количество возможных значений делимого x. Этот метод требует некоторых приемов, чтобы скомпенсировать ошибки округления. Следующий алгоритм даст вам верные результаты для деления беззнакового целого числа с усечением, то есть тот же результат, что дает инструкция DIV (спасибо Terje Mathisen, который изобрел этот метод): b = (количество значимых битов в d) - 1 r = 32 + b f = 2r / d Если f - целое число, тогда d - это степень от 2: переходим к случаю A. Если f - не целое число, тогда проверяем, меньше ли дробная часть f 0.5. Если дробная часть f < 0.5: переходим к случаю B. Если дробная часть f > 0.5: переходим к случаю C. случай A: (d = 2b) результат = x SHR b случай B: (дробная часть f < 0.5) округляем f вниз до ближайшего целого числа результат = ((x+1) * f) SHR r случай C: (дробная часть f > 0.5) округляем f вверх до ближайшего целого числа результат = (x * f) SHR r Пример: Предположите, что вы хотите разделить на 5. 5 = 00000101b. b = (количество значимых двоичных чисел) - 1 = 2 r = 32+2 = 34 f = 234 / 5 = 3435973836.8 = 0CCCCCCCC.CCC...(hexadecimal) Дробная часть больше, чем половина: используем случай C. Округляем f вверх до 0CCCCCCCDh. Следующий код делит EAX на 5 и возвращает результат в EDX: Код:
В случае B у вас будет следующее: Код:
Код:
Вы можете заменить медленную инструкцию умножения более быстрыми инструкциями, как это объяснено в главе 26.5. Следующий пример делит EAX на 10 и возвращает результат в EAX. Я выбрал r=17, а не 19, потому что это дает код, который легче оптимизировать, и он покрывает такое же количество значений x. f = 217 / 10 = 3333h, случай B: q = (x+1)*3333h: Код:
Последний раз редактировалось Mikl___; 08.06.2013 в 15:55. |
08.06.2013, 17:17 | #8 |
Пользователь
Регистрация: 26.02.2013
Сообщений: 12
|
Mikl___ благодарю!
У меня не хватило соображалки поискать там про magic numbers... |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм перевода чисел на языке Си. | AlekCaHdpyLLlka | Помощь студентам | 7 | 31.03.2012 13:02 |
Алгоритм перевода звука в код | timon023 | Помощь студентам | 0 | 17.12.2011 17:55 |
Нажатие на Enter без перевода на новую строку | notbugme | Общие вопросы C/C++ | 12 | 19.09.2010 20:39 |
Алгоритм перевода чисел из двоичной системы в десятеричную | _PROGRAMM_ | Помощь студентам | 5 | 16.03.2010 17:05 |
написал алгоритм перевода чисел из 10 в любую другую систему счисления...компилиться, но не выполняеться | STR78 | Общие вопросы C/C++ | 4 | 03.11.2008 17:07 |