Как избавиться от переполнения?

Question

[megorit]

Написал вот такую прогу для вывода ряда Фибоначи (0,1,1,2,3,5,8,13,21,34,55,89...):

#include <stdio.h>

void main(void) {
	double a, b;
	int n;

	a = 0;
	b = 1;

	system("TITLE fibonachi");
	system("COLOR F1");
	printf("Введите количество итераций (не меннее двух):\t");
	scanf("%d", &n); 
	printf("\n%.0f\n%.0f\n", a, b);

	n -= 2;
	while(n > 0) {
		a += b;
		printf("%.0f\n", a);
		n--;
		if(n > 0) {
			 b += a;
			 printf("%.0f\n", b);
			 n--;
		}
	}

	system("PAUSE");
}

Вот что получилось:

Если заменить на unsigned int и выводить как %u, то вот что получается:

Хотя где-то читал, что переполнения беззнаковых целых быть не должно.

Comments

[Oleg Shevelev]

Посмотрите big int.

Answer 1

[jcmvbkbc]

где-то читал, что переполнения беззнаковых целых быть не должно.

Нет никакой магии в беззнаковых целых, максимальное представимое число -- 2^(количество бит)-1, от больших чисел остаётся остаток по модулю 2^(количество бит). Это поведение описано стандартами языка C.

Answer 2

[AtomKrieg]

Использовать специальные библиотеки для больших чисел. А в вашей программе никак не избавиться.
Вычисления делаются через Double, у него есть ограничение на точность по мантиссе. Потом переводите в uint - все что в мантиссу не влезло превратилось в нули.

Answer 3

[Rsa97]

Что значит "переполнения беззнаковых целых быть не должно"?
То есть, объявив переменную как unsigned int я сразу получу возможность считать любую разрядность?
Конечно же переполнение есть, uint32 может содержать значения [0..4'294'967'295], uint64 - [0..18'446'744'073'709'551'615]. Хотите больше - используйте или пишите сами реализацию длинной арифметики.

Comments

[megorit]

А кстати, не подскажите как сделать собственный тип с разрядностью, например, 160? Такое возможно?

[megorit]

Переполнения быть не должно в том смысле, что можно просто "конкатенировать" две переменных типа uint. Если не хватает - еще раз, и так далее. Это я вычитал где-то во введении K&R.

[Rsa97]

Егор Марчук: Возможно. И с любой разрядностью тоже возможно. В C++ можно создать новый класс, перегрузив для него операторы арифметических действий, в чистом C - определить новый тип (typedef) и написать библиотеку функций для работы с ним (add, sub, mul, div и т.д.).
Сама реализация обычно делается на динамически выделяемом массиве, самые простые реализации держат числа в виде строк (массив символов), это упрощает ввод/вывод, но затратно на операциях и расходует память. Более сложные держат массив uint32/64, в зависимости от разрядности приложения, в этом случае сложнее становится ввод/вывод. Видел ещё вариант хранения в виде BCD, но там ассемблер поддерживал операции с такими числами.

Answer 4

[Антон Жилин]

Механизм переполнения отличается в signed и unsigned типах.

1. Пусть имеется переменная signed int num = INT_MAX; Тогда при ++num; что окажется в num -- unspecified. То есть может оказаться INT_MIN, а может 42.
   
2. Пусть имеется переменная unsigned int num = UINT_MAX; Тогда при ++num; в num обязано оказаться 0, в соответствии со стандартом.
   

Я так понял, что ваш источник под этим:

переполнения беззнаковых целых быть не должно

Имел в виду, что unsigned типы при переполнении безболезненно возвращаются (wrap) в 0, в отличие от signed.