Ldiv деление чисел типа long

Содержание

Ldiv деление чисел типа long

div, lldiv, imaxdiv

ОБЗОР

div_t div(int numerator, int denominator);
ldiv_t ldiv(long numerator, long denominator);
lldiv_t lldiv(long long numerator, long long denominator);
#include
imaxdiv_t imaxdiv(intmax_t numerator, intmax_t denominator);

Требования макроса тестирования свойств для glibc (см. feature_test_macros(7)):

_XOPEN_SOURCE >= 600 || _ISOC99_SOURCE || _POSIX_C_SOURCE >= 200112L;
или cc -std=c99

ОПИСАНИЕ

Функции ldiv(), lldiv() и imaxdiv() выполняют эту же функцию, деля числа соответствующего типа и возвращая результат в структуре с соответствующим именем, всегда с полями quot и rem того же типа, что и аргументы функции.

Ldiv деление чисел типа long

Stdlib.h — is the header of the general purpose standard library of C programming language which includes functions involving memory allocation, process control, conversions and others. It is compatible with C++ and is known as cstdlib in C++. The name… … Wikipedia

Stdlib.h — Saltar a navegación, búsqueda stdlib.h (std lib: standar library o biblioteca estándar) es el archivo de cabecera de la biblioteca estándar de propósito general del lenguaje de programación C. Contiene los prototipos de funciones de C para… … Wikipedia Español

stdlib.h — (std lib: standard library o biblioteca estándar) es el archivo de cabecera de la biblioteca estándar de propósito general del lenguaje de programación C. Contiene los prototipos de funciones de C para gestión de memoria dinámica, control de… … Wikipedia Español

stdlib.h — Стандартная библиотека языка программирования С assert.h complex.h ctype.h errno.h fenv.h float.h inttypes.h iso646.h limits.h locale.h math.h setjmp.h signal.h stdarg.h stdbool.h stddef.h stdint.h … Википедия

System (stdlib) — Saltar a navegación, búsqueda La función system() está incluída en la biblioteca cuya cabecera es . System permite ejecutar a su vez otras funciones como: cls , dir o pause . Por ejemplo, al escribir system ( pause ) se está… … Wikipedia Español

system (stdlib) — system() es una función del lenguaje de programación C incluida en su biblioteca estándar, dentro de la cabecera . Sirve para ejecutar subprocesos o comandos del sistema operativo. «system» permite ejecutar a su vez otras… … Wikipedia Español

Dao (programming language) — Infobox programming language name = Dao paradigm = Multi paradigm year = 2006 designer = Limin Fu latest release version = dao 1.0 preview latest release date = 2008 04 25 typing = statically typed or dynamically typed influenced by = C++, Lua,… … Wikipedia

Strtod — is a C language function that converts an ASCII string to a double precision value. It is utilized via the following sequence:double strtod(const char *restrict, char **restrict); [OpenGroup Technical Standards Documentation] Strtod is included… … Wikipedia

strtod — (сокр. от string to double, «строку в число двойной точности») функция языка Си, конвертирующая символ строки в число с плавающей запятой двойной точности. Определение функции имеет вид: double strtod ( const char * str, char ** endptr… … Википедия

Memory leak — A memory leak, in computer science (or leakage, in this context), occurs when a computer program consumes memory but is unable to release it back to the operating system. In object oriented programming, a memory leak happens when an object is… … Wikipedia

Структура программы на языке Си

В языке Си исходные файлы бывают двух типов:

· заголовочные, или h-файлы;

· файлы реализации, или Cи-файлы.

Имена заголовочных файлов имеют расширение «.h». Имена файлов реализации имеют расширения «.c» для языка Си и «.cpp», «.cxx» или «.cc» для языка C++.

Заголовочные файлы содержат только описания. Прежде всего, это прототипы функций. Прототип функции описывает имя функции, тип возвращаемого значения, число и типы ее аргументов. Сам текст функции в h-файле не содержится. Также в h-файлах описываются имена и типы внешних переменных, константы, новые типы, структуры и т.п. В общем, h-файлы содержат лишь интерфейсы, т.е. информацию, необходимую для использования программ, уже написанных другими программистами (или тем же программистом раньше). Заголовочные файлы лишь сообщают информацию о других программах. При трансляции заголовочных файлов, как правило, никакие объекты не создаются.

Файлы реализации, или Cи-файлы, содержат тексты функций и определения глобальных переменных. Говоря упрощенно, Си-файлы содержат сами программы, а h-файлы — лишь информацию о программах.

Представление исходных текстов в виде заголовочных файлов и файлов реализации необходимо для создания больших проектов, имеющих модульную структуру. Заголовочные файлы служат для передачи информации между модулями. Файлы реализации — это отдельные модули, которые разрабатываются и транслируются независимо друг от друга и объединяются при создании выполняемой программы.

В общем случае программа на языке Си имеет следующую структуру:

· раздел описания подключаемых библиотек;

· раздел описания процедур и функций.

Обязательным являются все разделы.

В разделе описания подключаемых библиотек после ключевого слова #include указывается имя подключаемого к программе библиотечного модуля. Имя модуля заключается в треугольные кавычки — . В этих модулях содержатся необходимые программе стандартные и пользовательские процедуры и функции, например, «#include ». В этом примере приведен важнейший модуль, в котором находятся основные стандартные процедуры и функции ввода/вывода. В дальнейших примерах программ будем применять эту конструкцию.

Любая программа, каков бы ни был ее размер, состоит из одной или более «функций», указывающих фактические операции компьютера, которые должны быть выполнены. В языке Си — это функция main. Обычно функциям можно давать любые имена, но main — это особое имя; выполнение программы начинается сначала с функции main. Это означает, что каждая программа должна в каком-то месте содержать функцию с именем main. Для выполнения определенных действий функция main обычно обращается к другим функциям, часть из которых находится в той же самой программе, а часть — в библиотеках, содержащих ранее написанные функции.

В разделе описания процедур и функций описываются нестандартные (пользовательские) процедуры и функции. Процедура или функция – это подпрограмма, т.е. специальным образом оформленная часть программы, которая выполняет необходимое в программе действие. Подробнее о процедурах и функциях рассказывается в разделе 8.

Обобщая все вышесказанное, структура программы на языке Си в упрощенном виде выглядит следующим образом:

#include //список подключаемых модулей

void main() //функция MAIN

int // раздел описания процедур и функций

Как видно из приведенного примера, текст программы на языке Си состоит из строк. Символы в строке записываются на одном уровне без надстрочных и подстрочных индексов. Для разделения некоторых конструкций языка используются пробелы. Пробелы формируются с помощью клавиш «пробел» и «Tab» на клавиатуре компьютера. Пробелы нельзя использовать внутри имён, чисел, специальных символов и служебных слов. По крайней мере 1 пробел должен быть между двумя последовательными именами, числами и служебными словами. Во всех других случаях наличие или отсутствие пробела не влияет на смысл программы. В том месте, где можно использовать 1 пробел, можно использовать любое количество пробелов. Конец строки считается пробелом, поэтому текст программы можно прерывать и переносить на другую строку в любом месте, где можно использовать пробел. Пробелы позволяют выделять структурные блоки программы и делают ее более наглядной, программа без такого структурирования плохо читаема и не понятна. Поэтому существует правило табулирования текста программы – выделения с помощью пробелов, символов табуляции и переводов строк вложенных блоков, циклов, условий.

Операторы разделяются между собой символом точка с запятой («;»). Пустым оператором считается оператор, который не выполняет никаких действий. На языке Си это может быть пробел с последующей точкой запятой.

Для пояснения текста программы используется комментарии.

Комментарии имеют вид (//текст) или (/*текст*/). Комментарий может охватывать несколько строк (используется форма «/*текст*/»), либо помещаться в одной строке (точнее, до конца строки), тогда используется форма: «// комментарий до конца строки».

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

Имена объектов в программе

Имена (идентификаторы) – условные обозначения для используемых в программе констант, типов, переменных, процедур и функций. Имя начинается с буквы и состоит из букв и цифр, т.е. в виде грамматики:

или в виде синтаксической диаграммы (рис.25):

1. Во многих реализациях языка количество символов в имени ограничено.

2. В качестве имен нельзя использовать служебные слова языка Си.

3. К буквам относится также символ «_» (подчёркивание).

4. В языке определены стандартные имена, которые можно использовать только в строго определенном смысле. Эти имена используются для обозначения стандартных констант, типов, файлов, процедур и функций.

Приведем перечень некоторых стандартных имён:

abs – абсолютное значение целого;

asctime – дать время;

atan, atan2 – арктангенс;

atof, atoi, atol – преобразовать в плавающее;

close – закрыть файл;

creat – создать файл;

difftime – определить отрезок времени;

ecvt – преобразовать число в строку;

exit, _exit – завершить выполнение программы;

fclose – закрыть файл;

fcvt – преобразовать double в строку с фиксированной точкой;

feof – проверка признака конца файла;

fgetc – взять байт из файла;

fgets – взять строку из файла;

filesize – дать размер файла;

findfirst, findnext – поиск файлов по шаблону;

floor – целая часть;

fmod – остаток от деления двух чисел;

fopen – открыть файл;

fprintf – форматный вывод в файл;

fputc – запись байта в файл;

fputs – запись строки в файл;

fread – читать из файла;

free – освободить память;

freopen – открыть файл повторно;

frexp – экспоненциальное представление;

fscanf – форматный ввод из файла;

fseek – позиционировать файл;

ftell – дать позицию в файле;

fwrite – писать в файл;

getc, getchar, getche, getch – взять байт из файла;

getcwd – дать текущий каталог;

gets – ввод строки;

index – найти литеру в строке;

inp, inpw – ввод из порта;

itoa – представление целого;

kbhit – проверка ввода с клавиатуры;

labs – абсолютное значение длинного;

ldiv – деление чисел типа long;

localtime – дать местное время;

log, log10 – логарифм;

lseek – изменить позицию в файле;

mkdir – создать каталог;

mktime – преобразовать время;

modf – дробная и целая часть числа;

open – открыть файл;

outp, outpw – вывод в порт;

printf, fprintf, sprintf – форматный вывод;

puts – вывод строки в файл;

rand – случайная величина;

read – читать блок из файла;

rename – переименовать файл;

rewind – установить указатель файла в начало;

rmdir – удалить каталог;

scanf – форматный ввод;

sin, sinh – синус, синус гиперболический;

spawn – создать процесс;

sprintf – форматный вывод в буфер;

sqrt – квадратный корень;

srand – инициализация случайной величины;

Илон Маск рекомендует:  Что такое код imagecolorexact

sscanf – форматный вывод из буфера;

strlen – дать длину строки;

strlwr – привести к нижнему регистру;

strspn – дать длину совпадающей подстроки;

strstr – найти подстроку;

time – дать время;

vprintf, vfprintf, vsprintf – форматный вывод;

write – писать в файл.

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.

Папиллярные узоры пальцев рук — маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Преобразуем в строку. Часть 1. Целые числа.

1. sprintf

Первое что приходит в голову это функция sprintf из стандартной библиотеки Си. Использовать её просто:

После чего в массиве buffer у нас лежит требуемая строка.
Но вот беда, sprintf это ведь функция форматированного вывода, которая много чего умеет и тянет за собой много другие функций стандартной библиотеки. Размер машинного кода при ее использовании увеличивается значительно. Например, даже минимальная версия sprintf из avr-libc (это то, что идет в составе WinAVR / AVR Toolchain) добавляет чуть менее 2 килобайт.

2. utoa, ultoa

В состав библиотек, поставляемых с компиляторами, часто включают функции преобразования числа в строку itoa, ltoa, utoa, ultoa. Вообще эти функции не стандартные, ног часто имеются в наличии и, в отличии от sprintf, не делают ничего лишнего.

3. Извлечение цифр делением на 10.

Готовые стандартные и не очень способы посмотрели. Теперь пришло время свои велосипеды изобретать. Первый самый очевидный способ это конечно деление на 10 и вычисление остатка в цикле.

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

4. Извлечение цифр делением на 10 с помощью функции div

Может попробовать использовать стандартную функцию div, которая возвращает сразу частное и остаток?

Но деление всё равно остается. К преимуществам этого и предыдущего метода можно отнести то, что они могут преобразовывать число в строку по любому основанию (если ёх чуть доработать), не обязательно 10.

5. Деление на 10 сдвигами и сложениями.

Если у целевого процессора нет аппаратной поддержки 32-х разрядного деления, то предыдущие два метода будут довольно медленными. Деление на 10 можно заменить на серию сдвигов и сложений. Вдохновившись книжкой «Алгоритмические трюки для программистов» (она-же «Hacker’s delight»), берём оттуда функцию деления на 10 с помощью сдвигов и сложений, заменив имеющееся там умножение на 10 (оно тоже «дорогое», на AVR по крайней мере) также сдвигами и сложениями. Модифицируем ее, чтоб она возвращала и частное и остаток:

Выглядит страшно и непонятно, но на самом деле всё просто. Сначала умножаем исходное число на 0.8 или 0.1100 1100 1100 1100 1100 1100 1100 1100 в двоичном представлении. Очень удобно, что дробь периодическая и удалось обойтись всего пятью сдвигами и четырьмя сложениями. Далее делим то, что получилось на 8, сдвигая на 3 разряда вправо. Получается исходное число делённое на 10 с точностью до единицы из-за ошибок округления. После находим остаток умножая полученное частное на 10 и вычитая его из исходного числа. Если остаток больше 9, то корректируем его и частное.
Сама функция использующее «быстрое» деление не отличается по виду от своих предшественниц.

6. Вычитание степеней 10.

Еще один популярный способ преобразования числа в строку, заключается в последовательном вычитании из исходного числа степеней 10, начиная с максимальной. Для этого понадобится таблица с этими степенями 10:

40 байт размером. И сама функция:

Работает очень просто, пока число больше текущей степени 10 вычитаем эту степень 10 из числа и считаем сколько раз вычлось. Потом переходим на меньшую степень 10. И так пока не доберёмся до 1. Цифры получаются сразу в нужном порядке, нужно только удалить ведущие нули.

Методы на двоично-десятичных числах.

Следующие три метода основаны на операциях с упакованными двоично-десятичными числами — binary coded decimals (BCD). В этом представлении каждая тетрада (4 бита) хранит одну десятичную цифру. В 32-х разрядной переменной можно таким образом хранить 8 десятичных цифр. В двоичном представлении в 2-х разрядной переменной 10 десятичных цифр. Поэтому эти методы дают урезанные результаты для чисел больше 99999999. Двоично-десятичные числа очень легко преобразуются в строку:

Собственно из операций с BCD нам нужно сложение и умножение на 2, которое успешно заменяется сложением числа с самим собой. Поэтому нужно только сложение:

Выглядит страшно и непонятно — опять какое-то хитрое побитовое колдунство. На самом деле, чтоб сложить два BCD нужно просто сложить их как обычные двоичные числа — строчка a += b. А потом к каждой тетраде значение которой оказалось больше 9 нужно добавить корректирующее число 6 с переносом бита в старшую тетраду. И к каждой тетраде из которой был перенос бита в старшую тетраду, нужно также добавить корректирующее число 6. Все остальные строки функции — как раз эта коррекция. В первых двух строках мы определяем все биты суммы a + b + 0x66666666ul, которые изменили своё значение из-за переноса бита из младшего разряда. В третей строка складываем наши два числа. В четвёртой — выделяем младшие биты переноса для каждой тетрады. В остальных — прибавляем 6 к тем тетрадам из которых был перенос бита. Вот так вот — без единого условного перехода.

7. Сложение степеней двойки.

Первый способ, хорошо всем знакомый еще со школьных уроков информатики, — сложение десятичных представлений степеней двойки, соответствующих единичным битам в преобразуемом числе:

7. Сложение степеней двойки с таблицей.

В предыдущем методе используется два сложения двоично-десятичных чисел. От одного из них можно избавиться беря степень двойки из таблицы:

Таблица содержит 30 элментов — 120 байт.

8. Horner’s method

В этом методе на каждом шаге удваиваем накопленный десятичный результат, если старший бит двоичного числа единица, то добавляем к результату единицу, двоичное число при этом умножаем на 2 (сдвигаем на бит влево).

Здесь уже две операции сложения BCD, но одна из них сложение с 1 и от неё одной можно избавиться.

При этом первый аргумент bcd_add может оказаться не корректным BCD, где младшая тетрада содержит цифру больше 9. Однако наша bcd_add это нормально прожевывает выдавая правильный результат. А вот если добавлять эту лишнюю единицу ко второму аргументы, то результат будет уже не правильным.
Количество итераций в цикле этого метода всегда будет равно разрядности числа, в отличии от предыдущих, где цикл закончится, как только в числе не останется единичных бит.

9. Извлечение цифр умножением на 10.

Идея заключается в том, что десятичные цифры можно извлекать со стороны старших бит числа и использовать умножение на 10 для перехода к следующему десятичному разряду. Для этого придётся представить наше двоично число как дробную часть, мысленно перенести запятую на сколько-то разрядов влево, в нашем случае это будет 27. При этом число будет состоять из 2^-27 долей. Чтоб извлекать десятичные цифры эта дробь должна состоять из каких-то десятичных долей пусть это будет 10^-9. Его нужно для этого умножить на 2^-27/10^-9 = 1.34217728. После этого биты начиная с 27 разряда будут содержать старшую десятичную цифру. Но это если исходное число было меньше 2^27. Если оно было больше, то две цифры со значением не более 31. Это надо учесть. Еще один момент — это переполнение. Начиная с чисела 3199999999 ((2^32-1) / 1.34217728) у нас будет переполнение на 1 разряд, которое тоже надо учесть. А как-же всё-таки умножить челое число на 1.34217728 и без изпользования плавающей точки? Всё так-же сдвиками и сложениями. И так вот, что получилось:

Как ни странно но это работает. Если кто-нибудь видел этот способ раньше — скажите мне, а то я могу претендовать на авторство.
Как видно при умножении пришлось использовать 40-ка битную арифметику — дополнительный байт для дробной части. Если дробную часть отбросить и использовать 32-х битную арифметику, то возникают ошибки округления, который достигают 7 для больших чисел. К сожалению в языке Си нет доступа к биту переноса и по этому перенос в/из дробной части пришлось организовывать вручную. Для эффективного использования бита переноса можно использовать ассемблерные вставки. Поскольку первая тестируемая платформа у нас будет avr-gcc, для него их и напишем, чисто ради спортивного интереса. С ними цикл умножения будет выглядеть так:

Бенчмарк

Теперь собственно та часть ради которой всё затевалось — сравнение скорости работы. Первой испытанной платформой будет будет AVR с использованием компилятора GCC.
Для методов разных типов время работы будет зависеть от разных факторов, например для методов основанных на делении на 10 время будет зависеть в большей степени от количества десятичных цифр, о есть от абсолютной величины числа и очень мало от самих этих цифр. Вычитание степеней 10 в цикле будет тем быстрее работать чем меньше сумма десятичных цифр составляющих число. То есть 1000000 обработается гораздо быстрее чем 999999. Методы основанные на двоично-десятичных числах будут быстрее работать если в исходном числе мало единичных бит — быстрее всего со степенями двойки. Время работы последнего метода будет зависеть только от абсолютной величины преобразуемого числа, но в меньшей степени чем методы с делением на 10. Итак в наборе для тестирования должны быть маленькие чила, большие числа, степени двойки, степени десяти, числа где много девяток.
Всякие тесты для AVR удобно проводить на симуляторе Simulavr — не нужно никакого железа, и многочисленных перепрошивок.
Для замера времени выполнения наших функций воспользуемся 16-ти разрядным таймером, тикающем на частоте ядра. Вывод на консоль через отладочный порт эмулятора. Оптимизация кода максимальная по скорости.
Вот что получилось в результате для 32-х разрядных чисел:

* после плюса размер зависимостей — таблицы или функции деления
** в скобках указаны результаты для варианта с ассемблерными вставками.

Лидирует в этом бенчмарке с не большим отрывом метод на быстром делении на 10 сдвигами и сложениями. К нему близко подобралось вычитание степеней 10. Следом метод с умножением на 10. методы с честным делением (включая utoa), как и ожидалось, самые медленные, особенно тот, что использует функцию ldiv, но и самые компактные. Время выполнения метода Хорнера практически не зависит от конвертируемого числа. sprintf работает относительно быстро, по сравнению с utoa. И не удивительно — у неё внутри используется метод похожий на utoa_fast_div, но накладные на разбор форматной строки и медленный вывод в буффер через fputc дают о себе знать.

UPDATE.
Результат для 16-х разрядных чисел:

Здесь опять с заметным преимуществом лидирует быстрое деление сдвигами/сложениями. Худший результат теперь у sprintf, ведь внутри она всё равно использует 32- разрядные числа.

UPDATE #2. Результаты для MSP430.

Результат для 16-х разрядных чисел:

Поскольку кроме MSP430 Launcpad-а с камнем MSP430G2231 других MSP430 у меня нет, тестировать пришлось на нем. Все функции разумеется в него не помещаются, по этому заливаются и тестируются по одной с помощью скрипта.
Как видно честное деление здесь почти вдвое медленнее чем у AVR.
UPDETE #3

Результаты для STM32.

Обсуждение результатов

Аутсайдером везде является функция использующая библиотечную функцию деления div. Несмотря на то, что она возвращает за один вызов и остаток и частное от деления, даже на STM32 аппаратным делением, она реализована программно и работает очень медленно. Очевидно этот способ использовать не стоит. Однако функция использующая встроенный оператор деления utoa_builtin_div, плетущаяся в конце на AVR и MSP430, на STM32 — в лидерах. Ничего удивительного, ведь в Cortex M3 есть аппаратное деление скажут многие, и будут не совсем правы — деление-то там есть, но оно не такое уж и быстрое (в скобках для utoa_builtin_div указано время, если заставить компилятор сгенерировать честное деление). Дело в том, что хитрый GCC при делении на константу использует хитрый трюк — заменяет деление на умножение на константу такую, что старшие 32 бита в 64 разрядном произведении, содержат исходное делимое, делённое на 10.

Илон Маск рекомендует:  Что такое код domattribute >name

Этот код эквивалентен примерно следующему:
uint32_t tmp = value;

Такой способ тоже описан в книжке «Алгоритмические трюки для программистов». Однако на AVR и MSP430 этот номер не пройдёт — там умножение 32*32 => 64 работает неприлично долго, дольше честного деления.
Еще utoa_builtin_div всегда имеет минимальный размер.
Всегда хороший, а зачастую лучший результат даёт деление на 10 сдвигами и сложениями utoa_fast_div. Это практически безусловный лидер по скорости и часто имеет вполне скромный размер. Этот метод всегда удачный выбор.
Любимое многими вычитание степеней десяти utoa_cycle_sub по размеру вместе с таблицей примерно совпадает сutoa_fast_div, но всегда немного уступает по скорости. Вобщем, тоже не плохой выбор.
Методы основанные на двоично десятичных числах работают не очень быстро, имеют не самый маленький размер и к тому-же выдают только 8 цифр результата (в моей реализации, можно получить все 10 цифр, но будет еще медленнее). Их лучше использовать не для преобразования двоичных чисел в строки, а для преобразования двоичных чисел в упакованные двоично десятичные, для последующей работы сними.
Особняком стоит метод с умножением на 10 utoa_fract. Он не выглядит очень привлекательным по среднему времени, однако его худшее время часто оказывается меньше, чем худшее время лидеров. У этого метода разница между лучшим и худшим относительно небольшая — он работает стабильно.

UPDATE.
Нашел еще один интересный и очень быстрый метод. Вот Вот здесь.

Описание того, как это работает по ссылке выше на английском. К сожалению, корректные результаты этот метод выдаёт только для 15-ти битных значений, зато очень быстро:
для AVR лучшее время — 133 такта, худшее — 167, среднее — 146.

Coming next.

Часть 2. Фиксированная и плавающая точка.

PS. Может быть кто знает еще какие нибудь методы преобразования чисел в строку?

Беззнаковая арифметика в Java

Как известно, в Java нет беззнаковых типов. Если в Си вы могли написать unsigned int ( char , long ), то в Java так не получится. Однако нередко возникает необходимость в выполнении арифметических операций именно с числами без знака. На первый взгляд кажется, что беззнаковые типы в принципе-то и не особо нужны (подумаешь, MaxInt для чисел со знаком меньше в два раза, если нужны числа больше, я просто возьму long и далее BigInteger ). Но основное различие на самом деле не в том, сколько различных неотрицательных чисел можно положить в signed или unsigned int, а в том, как над ними производятся арифметические операции и сравнения. Если вы работаете с бинарными протоколами или с двоичной арифметикой, где важен каждый используемый бит, нужно уметь выполнять все основные операции в беззнаковом режиме. Рассмотрим эти операции по порядку:

Преобразование byte в short (int, long)

Обычный каст (int) myByte выполнит расширение до 32 бит со знаком — это означает, что если старший бит байта был установлен в 1, то результатом будет то же самое отрицательное число, но записанное в 32-битном формате:

0xff -> 0xffffffff (-1)

Часто это не то, чего бы мы хотели. Для того, чтобы выполнить расширение до 32 бит без знака и получить 0x000000ff , в Java можно записать:

Сравнение без учёта знака

Для беззнакового сравнения есть лаконичная формула:

Для byte, short и long, соответственно, константы будут 0x80 , 0x8000 и 0x8000000000000000L .

Сложение, вычитание и умножение

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

Деление

Деление -256 на 256 даст нам -1. А нам бы хотелось, чтобы 0xffffff00 / 0x100 давало 0x00ffffff , а не 0xffffffff (-1) . Для byte , short и int решением будет переход к числам большей разрядности:

Но что делать с long ? Переходить на BigInteger в таких случаях обычно не вариант — слишком медленно. Остаётся только брать всё в свои руки и реализовывать деление вручную. К счастью, всё уже украдено до нас — в Google Guava есть реализация беззнакового деления для long , причём довольно шустрая. Если вы не используете эту библиотеку, проще всего выдрать кусок кода прямо из файла UnsignedLongs.java:

Чтобы код компилировался, придётся также позаимствовать реализацию compare(long, long) :

и Longs.compare(long, long) + flip(long) :

Побитовые сдвиги

The shift arithmetic left (SAL) and shift logical left (SHL) instructions perform the same operation; they shift the bits in the destination operand to the left (toward more significant bit locations). For each shift count, the most significant bit of the destination operand is shifted into the CF flag, and the least significant bit is cleared (see Figure 7-7 in the Intel®64 and IA-32 Architectures Software Developer’sManual, Volume 1).

То есть SAL добавили просто для симметрии, с учётом того, что для сдвига вправо есть разделение на логический и арифметический. Ну а Гослинг решил не заморачиваться (и, думается, правильно сделал).

Целочисленный тип long и деление

Я просто пишу процедуру для декомпозиции целого числа без знака в простые числа. он будет работать нормально, если я определяю тип данных как » int«, если изменить его на » длинный«, результат будет неправильным. Я не знаю, почему.

Кстати, я использовал Win-TC в качестве моего компилятора.

Спасибо за помощь Пола, я знаю, где не так. % d следует заменить на% ld.

Ваша функция DividerIsPrime , как написано в настоящее время, имеет дефект, который логически должен всегда возвращать True .

Причиной этого является то, что статус изменяется на каждой итерации. Даже если status=False достигнуто (число является составным, потому что модуль вышел на нуль для разделителя), то итерации будут продолжаться и в каждом случае status=True будет достигнуто на последней итерации, когда div >

Вы можете изменить это следующим образом:

Вы бы нашли это с помощью некоторого «unit test», например:

Очевидно, что существует гораздо более эффективные алгоритмы для «проверки правильности».

Как при делении двух целых чисел типа int получить вещественное число?

Результат равен 3, а мне-то нужно 3,142857143. Как это реализовать?

2 ответа 2

Очевидно, привести хотя бы одно из них к типу float:

В арифметических операциях все операнды приводятся к наиболее точному типу: short -> int -> long -> float -> double .

Всё ещё ищете ответ? Посмотрите другие вопросы с метками c# .net или задайте свой вопрос.

Похожие

Подписаться на ленту

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2020 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2020.11.11.35402

Преобразуем в строку. Часть 1. Целые числа.

1. sprintf

Первое что приходит в голову это функция sprintf из стандартной библиотеки Си. Использовать её просто:

После чего в массиве buffer у нас лежит требуемая строка.
Но вот беда, sprintf это ведь функция форматированного вывода, которая много чего умеет и тянет за собой много другие функций стандартной библиотеки. Размер машинного кода при ее использовании увеличивается значительно. Например, даже минимальная версия sprintf из avr-libc (это то, что идет в составе WinAVR / AVR Toolchain) добавляет чуть менее 2 килобайт.

2. utoa, ultoa

В состав библиотек, поставляемых с компиляторами, часто включают функции преобразования числа в строку itoa, ltoa, utoa, ultoa. Вообще эти функции не стандартные, ног часто имеются в наличии и, в отличии от sprintf, не делают ничего лишнего.

3. Извлечение цифр делением на 10.

Готовые стандартные и не очень способы посмотрели. Теперь пришло время свои велосипеды изобретать. Первый самый очевидный способ это конечно деление на 10 и вычисление остатка в цикле.

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

4. Извлечение цифр делением на 10 с помощью функции div

Может попробовать использовать стандартную функцию div, которая возвращает сразу частное и остаток?

Но деление всё равно остается. К преимуществам этого и предыдущего метода можно отнести то, что они могут преобразовывать число в строку по любому основанию (если ёх чуть доработать), не обязательно 10.

5. Деление на 10 сдвигами и сложениями.

Если у целевого процессора нет аппаратной поддержки 32-х разрядного деления, то предыдущие два метода будут довольно медленными. Деление на 10 можно заменить на серию сдвигов и сложений. Вдохновившись книжкой «Алгоритмические трюки для программистов» (она-же «Hacker’s delight»), берём оттуда функцию деления на 10 с помощью сдвигов и сложений, заменив имеющееся там умножение на 10 (оно тоже «дорогое», на AVR по крайней мере) также сдвигами и сложениями. Модифицируем ее, чтоб она возвращала и частное и остаток:

Выглядит страшно и непонятно, но на самом деле всё просто. Сначала умножаем исходное число на 0.8 или 0.1100 1100 1100 1100 1100 1100 1100 1100 в двоичном представлении. Очень удобно, что дробь периодическая и удалось обойтись всего пятью сдвигами и четырьмя сложениями. Далее делим то, что получилось на 8, сдвигая на 3 разряда вправо. Получается исходное число делённое на 10 с точностью до единицы из-за ошибок округления. После находим остаток умножая полученное частное на 10 и вычитая его из исходного числа. Если остаток больше 9, то корректируем его и частное.
Сама функция использующее «быстрое» деление не отличается по виду от своих предшественниц.

6. Вычитание степеней 10.

Еще один популярный способ преобразования числа в строку, заключается в последовательном вычитании из исходного числа степеней 10, начиная с максимальной. Для этого понадобится таблица с этими степенями 10:

40 байт размером. И сама функция:

Работает очень просто, пока число больше текущей степени 10 вычитаем эту степень 10 из числа и считаем сколько раз вычлось. Потом переходим на меньшую степень 10. И так пока не доберёмся до 1. Цифры получаются сразу в нужном порядке, нужно только удалить ведущие нули.

Методы на двоично-десятичных числах.

Следующие три метода основаны на операциях с упакованными двоично-десятичными числами — binary coded decimals (BCD). В этом представлении каждая тетрада (4 бита) хранит одну десятичную цифру. В 32-х разрядной переменной можно таким образом хранить 8 десятичных цифр. В двоичном представлении в 2-х разрядной переменной 10 десятичных цифр. Поэтому эти методы дают урезанные результаты для чисел больше 99999999. Двоично-десятичные числа очень легко преобразуются в строку:

Собственно из операций с BCD нам нужно сложение и умножение на 2, которое успешно заменяется сложением числа с самим собой. Поэтому нужно только сложение:

Выглядит страшно и непонятно — опять какое-то хитрое побитовое колдунство. На самом деле, чтоб сложить два BCD нужно просто сложить их как обычные двоичные числа — строчка a += b. А потом к каждой тетраде значение которой оказалось больше 9 нужно добавить корректирующее число 6 с переносом бита в старшую тетраду. И к каждой тетраде из которой был перенос бита в старшую тетраду, нужно также добавить корректирующее число 6. Все остальные строки функции — как раз эта коррекция. В первых двух строках мы определяем все биты суммы a + b + 0x66666666ul, которые изменили своё значение из-за переноса бита из младшего разряда. В третей строка складываем наши два числа. В четвёртой — выделяем младшие биты переноса для каждой тетрады. В остальных — прибавляем 6 к тем тетрадам из которых был перенос бита. Вот так вот — без единого условного перехода.

7. Сложение степеней двойки.

Первый способ, хорошо всем знакомый еще со школьных уроков информатики, — сложение десятичных представлений степеней двойки, соответствующих единичным битам в преобразуемом числе:

7. Сложение степеней двойки с таблицей.

В предыдущем методе используется два сложения двоично-десятичных чисел. От одного из них можно избавиться беря степень двойки из таблицы:

Таблица содержит 30 элментов — 120 байт.

8. Horner’s method

В этом методе на каждом шаге удваиваем накопленный десятичный результат, если старший бит двоичного числа единица, то добавляем к результату единицу, двоичное число при этом умножаем на 2 (сдвигаем на бит влево).

Илон Маск рекомендует:  Что такое код ifxus_tell_slob

Здесь уже две операции сложения BCD, но одна из них сложение с 1 и от неё одной можно избавиться.

При этом первый аргумент bcd_add может оказаться не корректным BCD, где младшая тетрада содержит цифру больше 9. Однако наша bcd_add это нормально прожевывает выдавая правильный результат. А вот если добавлять эту лишнюю единицу ко второму аргументы, то результат будет уже не правильным.
Количество итераций в цикле этого метода всегда будет равно разрядности числа, в отличии от предыдущих, где цикл закончится, как только в числе не останется единичных бит.

9. Извлечение цифр умножением на 10.

Идея заключается в том, что десятичные цифры можно извлекать со стороны старших бит числа и использовать умножение на 10 для перехода к следующему десятичному разряду. Для этого придётся представить наше двоично число как дробную часть, мысленно перенести запятую на сколько-то разрядов влево, в нашем случае это будет 27. При этом число будет состоять из 2^-27 долей. Чтоб извлекать десятичные цифры эта дробь должна состоять из каких-то десятичных долей пусть это будет 10^-9. Его нужно для этого умножить на 2^-27/10^-9 = 1.34217728. После этого биты начиная с 27 разряда будут содержать старшую десятичную цифру. Но это если исходное число было меньше 2^27. Если оно было больше, то две цифры со значением не более 31. Это надо учесть. Еще один момент — это переполнение. Начиная с чисела 3199999999 ((2^32-1) / 1.34217728) у нас будет переполнение на 1 разряд, которое тоже надо учесть. А как-же всё-таки умножить челое число на 1.34217728 и без изпользования плавающей точки? Всё так-же сдвиками и сложениями. И так вот, что получилось:

Как ни странно но это работает. Если кто-нибудь видел этот способ раньше — скажите мне, а то я могу претендовать на авторство.
Как видно при умножении пришлось использовать 40-ка битную арифметику — дополнительный байт для дробной части. Если дробную часть отбросить и использовать 32-х битную арифметику, то возникают ошибки округления, который достигают 7 для больших чисел. К сожалению в языке Си нет доступа к биту переноса и по этому перенос в/из дробной части пришлось организовывать вручную. Для эффективного использования бита переноса можно использовать ассемблерные вставки. Поскольку первая тестируемая платформа у нас будет avr-gcc, для него их и напишем, чисто ради спортивного интереса. С ними цикл умножения будет выглядеть так:

Бенчмарк

Теперь собственно та часть ради которой всё затевалось — сравнение скорости работы. Первой испытанной платформой будет будет AVR с использованием компилятора GCC.
Для методов разных типов время работы будет зависеть от разных факторов, например для методов основанных на делении на 10 время будет зависеть в большей степени от количества десятичных цифр, о есть от абсолютной величины числа и очень мало от самих этих цифр. Вычитание степеней 10 в цикле будет тем быстрее работать чем меньше сумма десятичных цифр составляющих число. То есть 1000000 обработается гораздо быстрее чем 999999. Методы основанные на двоично-десятичных числах будут быстрее работать если в исходном числе мало единичных бит — быстрее всего со степенями двойки. Время работы последнего метода будет зависеть только от абсолютной величины преобразуемого числа, но в меньшей степени чем методы с делением на 10. Итак в наборе для тестирования должны быть маленькие чила, большие числа, степени двойки, степени десяти, числа где много девяток.
Всякие тесты для AVR удобно проводить на симуляторе Simulavr — не нужно никакого железа, и многочисленных перепрошивок.
Для замера времени выполнения наших функций воспользуемся 16-ти разрядным таймером, тикающем на частоте ядра. Вывод на консоль через отладочный порт эмулятора. Оптимизация кода максимальная по скорости.
Вот что получилось в результате для 32-х разрядных чисел:

* после плюса размер зависимостей — таблицы или функции деления
** в скобках указаны результаты для варианта с ассемблерными вставками.

Лидирует в этом бенчмарке с не большим отрывом метод на быстром делении на 10 сдвигами и сложениями. К нему близко подобралось вычитание степеней 10. Следом метод с умножением на 10. методы с честным делением (включая utoa), как и ожидалось, самые медленные, особенно тот, что использует функцию ldiv, но и самые компактные. Время выполнения метода Хорнера практически не зависит от конвертируемого числа. sprintf работает относительно быстро, по сравнению с utoa. И не удивительно — у неё внутри используется метод похожий на utoa_fast_div, но накладные на разбор форматной строки и медленный вывод в буффер через fputc дают о себе знать.

UPDATE.
Результат для 16-х разрядных чисел:

Здесь опять с заметным преимуществом лидирует быстрое деление сдвигами/сложениями. Худший результат теперь у sprintf, ведь внутри она всё равно использует 32- разрядные числа.

UPDATE #2. Результаты для MSP430.

Результат для 16-х разрядных чисел:

Поскольку кроме MSP430 Launcpad-а с камнем MSP430G2231 других MSP430 у меня нет, тестировать пришлось на нем. Все функции разумеется в него не помещаются, по этому заливаются и тестируются по одной с помощью скрипта.
Как видно честное деление здесь почти вдвое медленнее чем у AVR.
UPDETE #3

Результаты для STM32.

Обсуждение результатов

Аутсайдером везде является функция использующая библиотечную функцию деления div. Несмотря на то, что она возвращает за один вызов и остаток и частное от деления, даже на STM32 аппаратным делением, она реализована программно и работает очень медленно. Очевидно этот способ использовать не стоит. Однако функция использующая встроенный оператор деления utoa_builtin_div, плетущаяся в конце на AVR и MSP430, на STM32 — в лидерах. Ничего удивительного, ведь в Cortex M3 есть аппаратное деление скажут многие, и будут не совсем правы — деление-то там есть, но оно не такое уж и быстрое (в скобках для utoa_builtin_div указано время, если заставить компилятор сгенерировать честное деление). Дело в том, что хитрый GCC при делении на константу использует хитрый трюк — заменяет деление на умножение на константу такую, что старшие 32 бита в 64 разрядном произведении, содержат исходное делимое, делённое на 10.

Этот код эквивалентен примерно следующему:
uint32_t tmp = value;

Такой способ тоже описан в книжке «Алгоритмические трюки для программистов». Однако на AVR и MSP430 этот номер не пройдёт — там умножение 32*32 => 64 работает неприлично долго, дольше честного деления.
Еще utoa_builtin_div всегда имеет минимальный размер.
Всегда хороший, а зачастую лучший результат даёт деление на 10 сдвигами и сложениями utoa_fast_div. Это практически безусловный лидер по скорости и часто имеет вполне скромный размер. Этот метод всегда удачный выбор.
Любимое многими вычитание степеней десяти utoa_cycle_sub по размеру вместе с таблицей примерно совпадает сutoa_fast_div, но всегда немного уступает по скорости. Вобщем, тоже не плохой выбор.
Методы основанные на двоично десятичных числах работают не очень быстро, имеют не самый маленький размер и к тому-же выдают только 8 цифр результата (в моей реализации, можно получить все 10 цифр, но будет еще медленнее). Их лучше использовать не для преобразования двоичных чисел в строки, а для преобразования двоичных чисел в упакованные двоично десятичные, для последующей работы сними.
Особняком стоит метод с умножением на 10 utoa_fract. Он не выглядит очень привлекательным по среднему времени, однако его худшее время часто оказывается меньше, чем худшее время лидеров. У этого метода разница между лучшим и худшим относительно небольшая — он работает стабильно.

UPDATE.
Нашел еще один интересный и очень быстрый метод. Вот Вот здесь.

Описание того, как это работает по ссылке выше на английском. К сожалению, корректные результаты этот метод выдаёт только для 15-ти битных значений, зато очень быстро:
для AVR лучшее время — 133 такта, худшее — 167, среднее — 146.

Coming next.

Часть 2. Фиксированная и плавающая точка.

PS. Может быть кто знает еще какие нибудь методы преобразования чисел в строку?

Имена объектов в программе

Имена (идентификаторы) – условные обозначения для используемых в программе констант, типов, переменных, процедур и функций. Имя начинается с буквы и состоит из букв и цифр, т.е. в виде грамматики:

или в виде синтаксической диаграммы (рис.25):

1. Во многих реализациях языка количество символов в имени ограничено.

2. В качестве имен нельзя использовать служебные слова языка Си.

3. К буквам относится также символ «_» (подчёркивание).

4. В языке определены стандартные имена, которые можно использовать только в строго определенном смысле. Эти имена используются для обозначения стандартных констант, типов, файлов, процедур и функций.

Приведем перечень некоторых стандартных имён:

abs – абсолютное значение целого;

asctime – дать время;

atan, atan2 – арктангенс;

atof, atoi, atol – преобразовать в плавающее;

close – закрыть файл;

creat – создать файл;

difftime – определить отрезок времени;

ecvt – преобразовать число в строку;

exit, _exit – завершить выполнение программы;

fclose – закрыть файл;

fcvt – преобразовать double в строку с фиксированной точкой;

feof – проверка признака конца файла;

fgetc – взять байт из файла;

fgets – взять строку из файла;

filesize – дать размер файла;

findfirst, findnext – поиск файлов по шаблону;

floor – целая часть;

fmod – остаток от деления двух чисел;

fopen – открыть файл;

fprintf – форматный вывод в файл;

fputc – запись байта в файл;

fputs – запись строки в файл;

fread – читать из файла;

free – освободить память;

freopen – открыть файл повторно;

frexp – экспоненциальное представление;

fscanf – форматный ввод из файла;

fseek – позиционировать файл;

ftell – дать позицию в файле;

fwrite – писать в файл;

getc, getchar, getche, getch – взять байт из файла;

getcwd – дать текущий каталог;

gets – ввод строки;

index – найти литеру в строке;

inp, inpw – ввод из порта;

itoa – представление целого;

kbhit – проверка ввода с клавиатуры;

labs – абсолютное значение длинного;

ldiv – деление чисел типа long;

localtime – дать местное время;

log, log10 – логарифм;

lseek – изменить позицию в файле;

mkdir – создать каталог;

mktime – преобразовать время;

modf – дробная и целая часть числа;

open – открыть файл;

outp, outpw – вывод в порт;

printf, fprintf, sprintf – форматный вывод;

puts – вывод строки в файл;

rand – случайная величина;

read – читать блок из файла;

rename – переименовать файл;

rewind – установить указатель файла в начало;

rmdir – удалить каталог;

scanf – форматный ввод;

sin, sinh – синус, синус гиперболический;

spawn – создать процесс;

sprintf – форматный вывод в буфер;

sqrt – квадратный корень;

srand – инициализация случайной величины;

sscanf – форматный вывод из буфера;

strlen – дать длину строки;

strlwr – привести к нижнему регистру;

strspn – дать длину совпадающей подстроки;

strstr – найти подстроку;

time – дать время;

vprintf, vfprintf, vsprintf – форматный вывод;

write – писать в файл.

Дата добавления: 2020-10-22 ; просмотров: 311 | Нарушение авторских прав

деления Зачем использовать div или ldiv в C/C++?

mod c++\ (4)

Да. C99 §7.20.6.2 / 2 гласит:

Функция div , ldiv и lldiv вычисляет число numer / denom и число numer % denom за одну операцию.

Есть ли конкретная причина использовать ldiv или div вместо ‘/’ или ‘%’ для разделения / модуля на две переменные?

Answer #1

Это должно быть быстрее, чем использование операторов / и % если вы хотите одновременно вычислить как фактор, так и остаток.

Answer #2

Ладно, это старше, но я просто споткнулся. Наиболее важная разница здесь: определяется результат div (). В стандарте C не говорится, как обойти фактор. Это связано с тем, что компилятор должен иметь возможность использовать реализацию машины, которая зависит от процессора. Существуют две различные реализации: — округление до -инфиниции — округление до 0.

div (), однако, указывается для последнего, и поэтому переносится.

Answer #3

Идея состоит в том, что результаты из / и% можно определить из одной инструкции DIV на процессоре. Таким образом, исторически, div () используется для обеспечения оптимизированного способа получения обоих.

Тем не менее, я обнаружил, что новые компиляторы в любом случае могут оптимизировать операцию / и% в один разделитель. Например, я видел эту оптимизацию на Microsoft Visual C ++. В этих случаях div () действительно не дает преимущества и, по сути, может даже быть медленным, если задействован вызов.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL