Здравствуйте. Долго думал как написать тему - решил написать как есть Задача - составить программу для нахождения суммы массива 10000 целых чисел произвольной разрядности (больше разрядности максимального целого числа) в полиномиальной системе счисления. Как я понимаю, чтобы представить полином произвольной разрядности, мне нужен массив, количество элементов в котором будет больше 2^32. Как мне такой массив получить? Ведь больше 2^32 он любого типа не может быть. И даже если прикрутить библиотеку BigInteger (прикручивал, к сожалению компоновщик ругается) массив сам больше не станет. Это принципиальный момент задачи я бы сказал, потом думаю реализовать на CUDA. Поэтому и язык C++. Подскажите создать такой массив, или может к задаче другой подход можно найти.
Да нет, ты заблуждаешься. Исходя из задания нужно только 10000 длинных целых. Реализовать это достаточно просто, и памяти много не потребуется. Полиномиальный вид это что-то вроде: a*N^0 + b*N^1 + ... + z*N^n, где N - основание системы счисления. Само длинное число будет представлять собой массив разрядов в N-ой системе счисления в Little-Endian (можно и по-другому, сути не меняет). Причем чем больше N, тем меньше потребуется элементов в массиве для хранения этого длинного целого. Если язык не важен, то я бы посоветовал использовать python или ruby, там длинные целые уже есть из коробки. Если нужно именно на C/С++, то могу поделиться реализацией длинных целых (есть как на чистом Си, так и на плюсах).
\\ChaOs//, ну вот допустим если для представления используется количество разрядов больше чем 2^32 - а это максимальная длинна массива - как тогда быть? Если есть реализация длинных чисел то скинь пожалуйста. Найденная мною на просторах интернета к сожалению не работает.
Нет...занаете, я подумал так.....вот как можно(4294967296 - числа произвольной разрядности значит числа больше этого): Число (1)(2)(3)(4)(5)(6)(7)(8)(9)(8)(7)(6)(5) И число (2)(2)(7)(8)(8)(4)(6)(9)(9)(9)(9)(9)(9) Они сверхдлинные больше максимальной разрядности (скобками разграничиваю так как число представлено в виде полинома, на манер первой строки little-endian). В результате получаем результат в массиве-результате: (3)(4)(10)(12)(13)(10)(13)(17)(18)(17)(16)(15)(14). Впринципе и так будет верно, но можно нормализовать. (3)(4)(0)(3)(4)(1)(4)(8)(9)(8)(7)(6)(5)(1) Ну и если из полиномиальной перевести в позиционную (благо все просто, 10ная) то получается число 15678984143043. Ну и соответственно сумму из 10000 чисел я думаю мы уместим в максимальную разрядность которую нам дает система. Как считаете?))) Думаю и без длинной арифметики можно обойтись.
Не сильное различие получается с true длинной арифметикой, у тебя тут только память не оптимально используется. Ну можно сделать и так
Хранить сразу несколько разрядов. Например, используя тип long для хранения одного разряда можно уместить 4 десятичных цифры (это если умножать планируешь длинные целые, иначе можно хранить 9 цифр). Хранить и производить операции так, как-будто работаешь с 10000-й системой счисления. Будет выглядить как-то так: PHP: #define BASE 10000 #define BASE_COUNT 4 struct LongNumber { unsigned long* data; unsigned long size; }; void LNAdd(struct LongNumber *source, struct LongNumber const *arg) { unsigned long tmp,t; int i=source->size-1, j=arg->size-1; while(j>=0) { if( i == -1) { _LNInsertToken(source, 0, 0); ++i; continue; } tmp=source->data[i]+arg->data[j]; if(tmp>=BASE) { if(!i) { _LNInsertToken(source, 0, 0); ++i; continue; } t=tmp/BASE; tmp-=t*BASE; source->data[i-1]+=t; } source->data[i]=tmp; --i; --j; } } void _LNInsertToken(struct LongNumber *arg, unsigned long pos, unsigned long data) { unsigned long *tmp; if(pos > arg->size-1) return; tmp = (unsigned long *)malloc((arg->size+1)*sizeof(long)); memcpy(tmp, arg->data, pos*sizeof(long)); tmp[pos] = data; memcpy(tmp+pos, arg->data + pos, (arg->size-pos)*sizeof(long)); free(arg->data); arg->data = tmp; }
\\ChaOs//, а у тебя нет библиотеки, чтобы подключив ее можно было использовать тип biginteger в программе?Я пытался скаченную непомню какую прикрутить, незаработало. Если есть можешь скинуть ссылку или на какой-нибудь файлообменник выложить. Нужно равнить сложение полиномов в представлении полиномов и как бы они просто были числами.
Есть, осталось от старой курсовой, которую делал на заказ. В архиве есть вариант на чистом Си и на С++ Скачать здесь
\\ChaOs// можешь еще подсказать, как ее правильно подключить. Начал писать: #include "stdafx.h" #include "longnumb.h" #include <iostream> #include <stdio.h> int _tmain(int argc, _TCHAR* argv[]) { LongNumb z=123456789123; system("pause"); return 0; } А VS 2010 выдает такие ошибки: error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall LongNumb::LongNumb(char const *)" (??0LongNumb@@QAE@PBD@Z) в функции _wmain D:\Игорь\proga2\dlinnie\dlinnie\dlinnie.obj dlinnie error LNK1120: 1 неразрешенных внешних элементов D:\Игорь\proga2\dlinnie\Debug\dlinnie.exe dlinnie Просто та библиотека которую нашел на днях тоже похожие ошибки выдавала. Пробовал что-то делать с гуглением- совсем никак((
Я когда-то использовал библиотеку MPIR - открытая, бесплатная, собирается без проблем под разные ОСи, имеет документацию подробную, огромное количество математических функций и реализации на Си и ассемблере (на выбор). Code: error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall LongNumb::LongNumb(char const *)" (??0LongNumb@@QAE@PBD@Z) в функции _wmain D:\Игорь\proga2\dlinnie\dlinnie\dlinnie.obj dlinnie А ты собери библиотеку сначала (cpp-файлы или c), а потом слинкуйся с ней, линкеру укажи lib-файл полученный. Либо просто включи все файлы сорсов либы в свой проект.
Добавить в проект файл cpp\c. (что-то типа добавить->существующий файл, либо в настройках проекта пути прописать). Заметил у тебя ошибку использования. Правильно так: Code: LongNumb num("1231241241244124");
