целочисленная арифметика Опции

[Obi]

Люди, подскажите, пожалуйста, где можно что-нибудь читнуть про целочисленную арифметику. Если можно, что-нибудь по-доступней.

[Arch_Grey]

Вопрос, конечно, интересный! Что-нибудь о Fixed point representation написано в описании АЛУ любого процессора. Применительно к теме форума есть интересная книга "The Scientist and Engineer’s Guide to Digital Signal Processing", где в начале 4-ой главы пару страниц отведено для описания представления целых чисел в цифровом компьютере. Книгу можно скачать тут http://www.dspguide.com.

[Obi]

Спасибо за ссылку. А вообще, может быть я плохо искал, но мне попадались либо общие слова или научные теоретизмы, слабо связанные с реальным миром. Хотя на руках уменя появилась более-менее подходящая книжка: Р.Грегори, Е.Кришнамурти "Безошибочные вычисления. Методы и приложения", 1988.

[Pathfinder]

На эту тему классная книжка "Алгоритмические трюки для программистов" не помню чья. Там подробно описаны эффективные реализации основных алгоритмов с использованием целочисленнойц арифметики. Говорят где-то есть в djvu формате.

[Sot]

Генри С. Уоррен, мл.
Алгоритмические трюки для программистов (Hacker's Delight), дополненное издание, 10.88 MB
http://rapidshare.de/files/7745099/WarrenA...m3_pdf.rar.html

или

Генри С. Уоррен, мл.
Алгоритмические трюки для программистов, 2.42 MB
http://rapidshare.de/files/5777980/Algo2Prog.rar.html

[AndrewKirs]

Obi, а что тебе нужно? Я занимался целочисленной реализацией заведомо FP-алгоритмов. Могу подсказать .

[Jools]

Obi, а что тебе нужно? Я занимался целочисленной реализацией заведомо FP-алгоритмов. Могу подсказать .

Хотелось бы узнать общие действия или рекомендации по переводу FP-алгоритмов в целочисленные. Сейчас тоже подхожу к этому - хотелось бы послушать опытных.

Заранее спасибо.

[AndrewKirs]

Например, так. FP-число хранится как два integer. Первый содержит целую часть, второй - дробную в целочисленных терминах. Скажем, на нее выделяется 16 бит, из которых старший используется для проверки переполнения. Остается 15 бит (dec=0..32767 или hex=0..7FFF), и числу 0.5 будет соответствовать 3FFF. Налицо некоторая потеря точности, поэтому надо аккуратно смотреть, сколько бит нужно.

Дальше операции ведутся параллельно над целой и дробной частями. То есть сложение двух FP-чисел сведется к сложению отдельно целых и дробных частей. Для дробных надо анализировать старший бит.
Если он равен 1, значит произошло переполнение => увеличиваем на 1 целую часть и обнуляем старший бит дробной.

[tag]

...сейчас под рукой нету, есть такая книга "Программы для микропроцессоров" автор Гутников или Гуртовцев (не помню), там подробно и с примерами описывается целочисленная арифметика, арифметика с фиксированной и плавающей запятой... на примере ещё I8085

[GetSmart]

Кто-нибудь знает, почему я не могу скачать с rapidshare.de эти файлы?

[Oldring]

Хотелось бы узнать общие действия или рекомендации по переводу FP-алгоритмов в целочисленные.

В Кнуте очень подробно описываются математические основы плавающей арифметики без скидок на слабое знание программистом математики. Если хотите действительно разобраться в тонкостях её реализаций - выбросите все эти книги для чайников прочтите соотвествующие разделы Кнута обязательно, хоть это иногда и непросто из-за чрезмерной любви автора к ассемблеру его любимой абстрактной машины

[AndrewKirs]

Была такая книга: В.К.Злобин, В.Л.Григорьев Программирование арифметических операций в микропроцессорах, М.,"Высшая школа", 1991, 303 стр.
Возможно сейчас, когда сканируют все подряд, она найдется где-нибудь в электронном виде.
Там описаны процессор 8086/8087, стандарт IEEE-754 и приведены алгоритмы целочисленной реализации операций с плавающей точкой (на ассемблере 8086).

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

[=GM=]

Например, так. FP-число хранится как два integer. Первый содержит целую часть, второй - дробную в целочисленных терминах. Скажем, на нее выделяется 16 бит, из которых старший используется для проверки переполнения. Остается 15 бит (dec=0..32767 или hex=0..7FFF), и числу 0.5 будет соответствовать 3FFF. Налицо некоторая потеря точности, поэтому надо аккуратно смотреть, сколько бит нужно.

Дальше операции ведутся параллельно над целой и дробной частями. То есть сложение двух FP-чисел сведется к сложению отдельно целых и дробных частей. Для дробных надо анализировать старший бит.
Если он равен 1, значит произошло переполнение => увеличиваем на 1 целую часть и обнуляем старший бит дробной.

Тут вы немного перегнули палку. Сложение двух FixedPoint чисел m.n не сводится к отдельному сложению целых и дробных частей. Достаточно такие числа складывать, как целые числа m+n разрядности. Точка в результате (m+1).n будет на том же самом месте. Все переносы между целыми и дробными частями осуществляются автоматически.

[AndrewKirs]

Тут вы немного перегнули палку. Сложение двух FixedPoint чисел m.n не сводится к отдельному сложению целых и дробных частей. Достаточно такие числа складывать, как целые числа m+n разрядности. Точка в результате (m+1).n будет на том же самом месте. Все переносы между целыми и дробными частями осуществляются автоматически.

Это я несколько упрощенно написал, т.к.не хотел загромождать деталями. На самом деле, у меня FP-число хранится как два 16-битных WORD. Все это хозяйство реализуется на MMX, и в одном его 64-битном регистре хранится 4 таких вот дробных части, а в другом - 4 целых. Тот же алгоритм (билинейная интерполяция) перенесен на SSE2, там регистр в два раза больше, поэтому влезает по 8 штук.
Соответственно, старший бит используется под проверку переполнения.

[_artem_]

Помоему эта книжка лучше чем хакерс делайт хотя и бесплатная .

"Algorithms for programmers Ideas and asoruce code "

http://www.jjj.de/fxt/#fxtbook
http://www.jjj.de/fxt/fxtbook.pdf.gz