Почему математические вычисления выводятся неправильно?
Я написал код для преобразования десятичных чисел в двоичные числа на двух разных компиляторах: dev C++ и codeblock.
#include <stdio.h>
#include <math.h>
int main(){
int n=0, nhiphan=0, m=0, thuong=0, du=0;
scanf("%i", &n);
while(n>0){
du=n%2;
nhiphan = nhiphan + (du)*pow(10,m);
m++;
thuong = n/2;
n=thuong;
}
printf("%i\n", nhiphan);
}
Когда я попробовал 6, разработчик дал правильный ответ: 110, но блок кода выдал результат 109, даже мой онлайн-судья дал неправильный ответ. Я проверил номер других на устройстве C, он все равно дает правильный ответ, но кодовый блок иногда дает неправильные ответы.
Есть ли способ проверить, как он работает и как предотвратить неправильный ответ?
Использование (32-битного) int для представления двоичного числа в базе 10 работает только для двоичных чисел длиной до 10 бит (то есть до 2047), прежде чем вы получите переполнение.
@PaulHankin: Re: «pow возвращает двойное число, поэтому я ожидаю, что у вас есть ошибки округления»: это не ошибки округления. 10^m точно представимо в формате, обычно используемом для double для неотрицательных m до 22, поэтому нет необходимости округлять результат. Если pow не возвращает 10^m для этих случаев, это потому, что оно было реализовано неправильно, а не потому, что числа с плавающей запятой требуют округления.
Не работайте с двоичными числами, пытаясь закодировать их как цифры 0 и 1 в десятичном числе. Это расточительно и весьма ограничено шириной int. Выполнение scanf("%i", &n) преобразует десятичные входные данные в двоичные; результат в двоичном виде в n. Просто проверьте его биты и напрямую выведите «0» или «1».
@EricPostpischil, библиотеки FP относительно часто реализуют функции, которые иногда дают результаты, которые неправильно округлены, в пределах некоторой ошибки. В пределах 1 ульпа, скажем. Если это делается намеренно, обычно ради скорости, то в моей книге «ошибка округления» подходит лучше, чем «неправильно реализовано». То, что правильно округленный результат является точным, не имеет значения для этого анализа, если граница ошибки составляет не менее 1 ulp, что не так уж редко для реализаций pow().
@JohnBollinger: такие библиотеки следует рассматривать как неправильно реализованные. Если бы у вас была функция целочисленного деления, которая иногда возвращала слишком большое частное, это было бы расценено как неправильная реализация. Если бы у вас была функция связанного списка, которая иногда удаляла элемент из списка, это было бы расценено как неправильная реализация. Функция, которая возвращает неправильный результат, хотя правильный результат может быть возвращен, реализована неправильно.
@EricPostpischil, если бы эти гипотетические функции целочисленного деления и т. д. вели себя так, как они были задуманы, то это лучше всего было бы охарактеризовать как «плохо спроектированное», а не «неправильно реализованное». Функция pow(), предназначенная для возврата результата в пределах 1 ульпа от правильно округленного результата, не может быть признана неправильной, если она возвращает результат, отличающийся от правильно округленного на 1 ульп. При желании к такой конструкции pow() можно придраться, но дело в том, что такие конструкции распространены, и это нужно учитывать при работе с математикой fp.
@EricPostpischil, вы бы также считали, скажем, pow(9, 0.5) неправильно реализованным, если он не возвращает точно 3? Или если pow(0.25, 0.5) не возвращает именно 0.5 и т. д.?
Glibc, например, определяет ошибку 1ulp, связанную с pow() на большинстве архитектур, включая i686 и x86_64.
@WeatherVane: Да.
@JohnBollinger: Тот факт, что библиотека указывает привязку к ошибке, не означает, что мы должны ее принять. Если бы в процедуре сортировки указано, что она часто сортирует все правильно, но иногда меняет местами два элемента, я бы признал, что она соответствует ее спецификациям, но не принял бы ее как правильно реализованную процедуру сортировки. Уровень развития математических библиотек с плавающей запятой продвинулся вперед. Есть хорошие реализации с открытым исходным кодом. Следует настаивать как минимум на качестве общедоступного исходного кода.
Тем не менее, в целом сообщество принимает его для функций FP, @EricPostpischil. В режиме FP разумным решением является пожертвовать небольшой точностью в обмен на скорость, поскольку многим приложениям скорость требуется больше, чем точность, и в любом случае нельзя ожидать точных результатов FP. Если кому-то требуются функции FP, которые всегда возвращают правильно округленный результат, то их можно получить, но на это нужно обратить внимание, это одна из деталей, которую должен иметь в виду любой программист с FP.
@JohnBollinger: О «Тем не менее, в целом сообщество принимает это для функций FP»: Не надо. Времена меняются. Доступен новый код. Приведены новые доказательства. Преобладание людей, принимающих плохой код, не является поводом присоединяться к ним. Re: «В режиме FP разумно пожертвовать небольшой точностью в обмен на скорость»: это было разумное дизайнерское решение несколько десятилетий назад. Времена меняются. Есть новый код, и он обеспечивает хорошую производительность при высокой точности, иногда даже лучшую производительность, чем старый код с меньшей точностью. Перестаньте принимать плохой код.
@EricPostpischil, конечно, прогресс есть, но, насколько я могу судить, конкретный прогресс, который вы здесь хотите, не был достигнут. Рассмотрим эту статью 2024 года, в которой представлена эффективная, правильно округленная pow() реализация, которая довольно хорошо сравнивается с другими правильно округленными реализациями. Авторы, похоже, воодушевлены тем, что он всего на 26% медленнее, чем в пределах 1-ulp glibc pow().
В конечном счете, если назвать pow(), например, ОП, «неправильно реализованным», создается неправильное впечатление. Это предполагает, что вам не следует ожидать таких реализаций, что в настоящее время не является хорошим советом. С другой стороны, тот факт, что результат может быть округлен неправильно, хорошо описан, поскольку он может содержать ошибку округления, и поощрение программистов к осознанию такой возможности сослужит им хорошую службу.
@JohnBollinger: О «glibc Within-1-ULP pow()»: Glibc не говорит, что у него есть внутри-1-ULP pow. Там написано, что максимальная ошибка составляет 1 ULP. Это критическая разница. Если подпрограмма возвращает результат в пределах 1 ULP от идеального математического результата, то она возвращает точные результаты для представимых значений. Если его максимальная ошибка составляет 1 ULP, а не в пределах 1 ULP, он может возвращать неверные результаты для представимых значений…
… В наивно написанном коде неточность реализации pow чаще является провалом, чем производительность, как мы часто видели в вопросах о переполнении стека. В хорошо написанном коде pow редко используется интенсивно, поэтому замедление реализации на 26% — это небольшая плата за большую точность. (Не то, чтобы я доверял документации glibc. Утверждения «В идеале ошибка для всех функций всегда меньше 0,5ulps в режиме округления до ближайшего. Используя биты округления, это также возможно…» являются ложными. Максимум, на что способна оценка ошибки. be меньше или равно ½ ULP, и, опять же, эта разница имеет значение.)
@EricPostpischil, я не согласен с вами по поводу значения моей формулировки, но конкретные границы ошибок Glibc pow() не имеют значения. Я признаю, что вы сочли бы снижение производительности в 26% приемлемым в данных обстоятельствах, но (i) не все с этим согласятся, и (ii) этот алгоритм является совершенно новым в этом году, поэтому он еще не учитывался при принятии чьих-либо решений. Если pow() генерирует неправильно округленный результат, то я не понимаю, как можно отрицать, что это ошибка округления. Учение о том, что функции fp могут иметь ошибки округления, хорошо помогает неопытным программистам [...]
[...] независимо от того, считаете ли вы, что они должны иметь ошибки округления или нет.
@JohnBollinger: Re: «Если pow() генерирует неправильно округленный результат, то я не понимаю, как можно отрицать, что это ошибка округления»: потому что обычно это не неправильно округленный результат. Округления, использованные при расчете, вероятно, были выполнены правильно в соответствии со спецификацией IEEE 754. Ошибка, вероятно, связана с тем, что она была неправильно рассчитана или вычислена из-за неиспользования полинома, рассчитанного с необходимой точностью, или из-за того, что в расчетах не использовалась достаточная точность для получения хорошего ответа. Эти вещи являются выбором, а не случайностью или требованием чисел с плавающей запятой.
@JohnBollinger: Re: «Учение о том, что функции fp могут иметь ошибки округления, хорошо помогает неопытным программистам»: Нет, обучение неопытных программистов тому, что они могут получать ошибки, пойдет им на пользу. Но их следует научить, что причины этих ошибок — это выбор разработчиков библиотечных подпрограмм, а не необходимость арифметики с плавающей запятой. Их не следует учить, что эти ошибки вызваны ошибками округления; их следует научить, что они вызваны выбором, сделанным людьми.
@OP Если код C++, почему вы отметили его как c ? а не c++?
Ответы 1
Я предлагаю добавить и использовать вашу собственную реализацию pow(), поскольку кажется, что различия в ваших выводах могут быть связаны с тем, что разные компиляторы имеют свои собственные реализации pow(), которые могут быть несовместимы с вашим кодом.
Этот код использует собственную реализацию pow() как ipow() и адаптирован на основе превосходного вклада Элиаса Ярркова, найденного здесь, на stackoverflow.
Помимо этого, я лишь немного изменил ваш код:
- обновил все целые числа до unsigned long long, чтобы обеспечить обработку большего числа, и
- удален
scanf()и напрямую назначен переменнойn, чтобы включить работоспособный код на godbolt.
Акцент: логика вашего кода не изменилась: ваш код работает.
#include <stdio.h>
unsigned long long ipow(unsigned long long base, unsigned long long exp)
{
unsigned long long result = 1;
for (;;)
{
if (exp & 1)
result *= base;
exp >>= 1;
if (!exp)
break;
base *= base;
}
return result;
}
int main()
{
unsigned long long n=(255<<8)+255; /* Should give 1111111111111111 (16 ones)*/
unsigned long long nhiphan=0, m=0, thuong=0, du=0;
while(n>0)
{
du=n%2;
nhiphan = nhiphan + (du)*ipow(10,m);
m++;
thuong = n/2;
n=thuong;
}
printf("%llu\n", nhiphan);
}
Выход:
1111111111111111
Хотя вы можете радоваться тому, что ваши усилия и размышления сработали, приведенная выше реализация не является рекомендуемым решением.
Следующая реализация, по моему мнению, лучше. Он обеспечивает строковое представление двоичной формы числа. Кроме того, он обеспечивает более удобное форматирование, которое облегчает чтение выходных данных и помогает обеспечить правильность вывода.
Работоспособный код находится здесь.
#include <stdio.h>
/*---------------------------------------------------------------
toBase2Str()
Returns a string binary representation of an input number.
Params: number to convert and the size of the data type
so we know how many leading zeros to pad
*---------------------------------------------------------------*/
char *toBase2Str(unsigned long long num, size_t nsize)
{
static char szRes[100];
long iii=0, bitpos = nsize*8;
while (bitpos-- && iii < sizeof(szRes)-1)
{
szRes[iii++] = (char) (((num >> bitpos) & 0x01) + '0');
if (!(bitpos%8))
szRes[iii++] = ' '; /*add space every 8 digits */
}
szRes[iii] ='\0'; /*cap it*/
return szRes;
}
int main()
{
unsigned char cnum = 0x0F;
unsigned int num = 0x0000FFFF;
unsigned long long lnum = 0xFFFFFFFF;
printf("%s \n", toBase2Str(cnum, sizeof(cnum)));
printf("%s \n", toBase2Str(num, sizeof(num)));
printf("%s \n", toBase2Str(lnum, sizeof(lnum)));
return (0);
}
Выход:
00001111
00000000 00000000 11111111 11111111
00000000 00000000 00000000 00000000 11111111 11111111 11111111 11111111
Не делай это. Вычисление двоичных чисел в десятичных — это ужасно и совершенно ненужно.
@EricPostpischil - как обычно, ты прав на 100%. Однако, с вашего разрешения, я бы попросил вас оставить это в силе по двум причинам, которые мне кажутся хорошими: 1.) он показывает возможности C (хотя и НЕ лучшая практика, никакие стандарты на самом деле не нарушаются, и 2.) OP может принимать утешение в том, что его/ее код работает — концепция верна. ОП может узнать о лучших реализациях и логике по мере продвижения в пути C. РЕДАКТИРОВАТЬ - вот что - я добавлю лучшую реализацию, чтобы помочь в руководстве ОП.
powвозвращает двойное значение, поэтому я ожидаю, что у вас есть ошибки округления. Вместо этого начнитеmс 1 и умножайте его на 10 каждый раз в цикле.