Всем привет.
Сделал упражнения к книге Бьерна Страуструпа "Программирование. Принципы и практика
использования С++".
Текст упражнений такой:
Мое решение для этих упражнений такое:
#include <iostream>
#include <cmath>
#include <limits>
using namespace std;
#define LOG_STEPS
void how_cells(double seeds)
{
double sum = 0;
int cell_numb=0;
double seed_count=0;
for ( cell_numb=1, seed_count=1.0;
cell_numb <= 64;
cell_numb++,seed_count*=2.0
)
{
sum += seed_count;
#ifdef LOG_STEPS
cout << cell_numb << " " << fixed << seed_count << " " << fixed << sum << endl;
#endif //LOG_STEPS
if (sum>=seeds)
{
cout << "Answer is " << cell_numb << endl;
break;
}
}
}
int main()
{
//До какой клетки дойдем, чтобы получить хотя бы 1000 зерен риса в сумме
cout << "Task#1. Cell numb if 1000 seeds:" << endl;
how_cells(1000);
//До какой клетки дойдем, чтобы получить хотя бы 1000000 зерен риса в сумме
cout << "Task#2. Cell numb if 1.000.000 seeds:" << endl;
how_cells(1000000);
//До какой клетки дойдем, чтобы получить хотя бы 1000000000 зерен риса в сумме
cout << "Task#3. Cell numb if 1.000.000.000 seeds:" << endl;
how_cells(1000000000);
//До какой клетки дойдем, чтобы получить максимальное значение для int зерен риса в сумме
cout << "Task#4. Cell numb in int max:" << endl;
cout << "Max of int: " << numeric_limits<int>::max() << endl;
how_cells(numeric_limits<int>::max());
//До какой клетки дойдем, чтобы получить максимальное значение для double(только мантисса) зерен риса в сумме
cout << "Task#5. Cell numb in double max:" << endl;
//Должно быть такое значение 9223372036854775808.0 по замыслу Страуструпа, но младшие декады теряются
cout << "Max of double (mantissa): " << 9223372036854775808.0 << endl; //берется только мантисса pow(2.0,63.0) != numeric_limits<double>::max()
how_cells(9223372036854775808.0); //берется только мантисса pow(2.0,63.0) != numeric_limits<double>::max()
system("pause");
return 0;
}
При вычислении номера клетки для того чтобы в сумме получить 1000, 1000000, 1000000, 217483647(максимальное значение для int) все хорошо. А вот для максимального значения double не все однозначно. Явно в упражнении не говорится, но Страуструп как я понял говорит только о мантиссе и количестве знаков в ней, порядок в расчет вроде как не берется (иначе максимальное число при потере знаков в мантиссе было бы в степени 308). Поэтому если говорить о мантиссе я думаю, что подразумевалось число 9223372036854775808, т.е 63-я клетка и сумма для нее. Но по факту получаем на этой клетке 9223372036854775800. И сюдя по выводимым значениям начинается это искажение гораздо раньше на значениях 72057594037927936 больше, т.е. сумма после 56-й клетки. Но как тогда определить это искажение в программе? Можно конечно задать константу, в которой будет значение 72057594037927936, вроде оно не перетрется при записи, но думаю такое решение не до конца верно . Отсюда вопрос: какое максимальное значение мантиссы без потери знаков(младшие декады) можно задать для типа double и можно ли его узнать стандартными средствами библиотеки?
upd. Нашел средства библиотеки, которые обеспечивают вывод количества доступных цифр в мантиссе без искажений. Вот пример кода:
#include <iostream>
#include <cfloat> //DBL_DIG
#include <limits> //std::numeric_limits<double>
using namespace std;
int main()
{
cout << "Number of digits (in decimal base) that can be represented without change." << endl;
cout << "pure C. <cfloat>. Answer: " << DBL_DIG << endl;
cout << "C++. <limits>.std::numeric_limits<double>. Answer: "<< numeric_limits<double>::digits10 << endl;
//Нет искажения (15 цифр)
cout << fixed << 999999999999999.0 << endl;
//Есть искажение по последней цифре (16 цифр)
cout << fixed << 9999999999999999.0 << endl;
//Нет искажения (16 цифр)
cout << fixed << 9999999999999912.0 << endl;
//Нет искажения (17 цифр). Наш случай макисмального неискаженного числа.
//Т.е. вышли за 15 цифр.
cout << fixed << 72057594037927936.0 << endl;
system("pause");
return 0;
}
Получается, что для типа
double это гарантировано пятнадцать цифр. Можно было бы получить это значение в программе и потом считать кол-во цифр суммы при добавлении каждой последующей клетки. Однако как видно при выполнении программы при превышении 15-ти цифр не всегда наблюдается искажение. И в нашем случае с доской искажения нет до 17-ти цифр (72057594037927936 , сумма после 56-й клетки). Получается, что определить кол-во цифр для мантиссы при которых еще не будет искажения для каждого конкретного случая (в частности для нашего) средствами библиотек C/C++ не представляется возможным. Не понятно возможно ли определить клетку и соответствующую ей сумму (клетка 56, сумма 72057594037927936 ) в автоматическом режиме а не просто сравнением с константой полученной более ранним прогоном программы. На данный момент такого варианта не вижу. Может кто-то все таки знает как?
upd Написал вариант решения задачи с типом unsigned long long (8 байт) получается вычислить количество зерен полностью (2^64). В него влезает кол-во зерен всей доски. Если бы было на одно зерно больше то не влезло бы. Решение:
#include <iostream>
#include <cmath>
#include <limits>
using namespace std;
unsigned long long calc_sum()
{
unsigned long long sum = 0;
int cell_numb=0;
unsigned long long seed_count=0;
for ( cell_numb=1, seed_count=1;
cell_numb <= 64;
cell_numb++,seed_count*=2
)
{
sum += seed_count;
cout << cell_numb << " " << seed_count << " " << sum << endl;
}
return sum;
}
int main()
{
cout << "Max of unsigned long long: " << numeric_limits<unsigned long long>::max() << endl << endl;
unsigned long long total_seed_count = calc_sum();
cout << endl << "Total: " << total_seed_count << endl;
system("pause");
return 0;
}
Но это не решает поставленную Бьерном задачу с типом double.
