Integer overflow - Aneb, když jsou vám trenky těsné – Pascal – Fórum – Programujte.com

Předně, byl jsem na vahách, jestli by nebylo rozumnější umístit vlákno do diskuse Matematika, protože přece jen asi způsob řešení mého problému nebude tolik odlišný v různých jazycích..

Tak tedy - typ Integer, alespoň tak, jak jej používám, je roven typu LongInt a tedy rozmezí - 2^(2^5 -1) .. 2^(2^5 -1) - 1, což je odhadem +- 10^9 a to je vysloveně málo místa na jakoukoliv větší práci.

Konkrétněji - ať už jsem nedávno vytvářel "pokus o implementaci RSA algoritmu" nebo si v současné době píšu prográmek na testování prvočísel, vždycky jsem narazil na to, že jsem se nějak potřeboval vyhnout omezením délky čísel. (tedy přesněji, ne vyhnout, jen je oddálit - s tím, že dříve či později se jakékoliv pokusy o odstranění omezení zastaví např. na velikosti mého HDD, jsem se již kdysi dávno psychicky smířil :) )
To se podle mě dá řešit (a já to tak dosud dělal) například tak, že si připravím nějaký konkrétní typ spojového seznamu, kde v každém "node" bude jedna cifra daného čísla. Takže pokud si přečtu dané číslo cifru po cifře (nejspíše ze souboru, protože běžný vstup, pokud se nepletu, taky přijímá pouze max cca 255 znaků), přitom si pro ten spojový seznam napíšu všechny základní početní operace a jiné potřebné procedury, pak jsem schopen celkem rozumně fungovat.

Mě by ale celá záležitost zajímala z pohledu rychlosti práce s takovou strukturou a její časová optimalizace.
Aneb, je práce s takovým spojovým seznamem mnohem pomalejší než s obyčejným integerem?

A hned mě přitom napadá např. výše zmiňovaný RSA algoritmus - to musí být přece vysoce časově optimalizovaný nástroj pro práci s dlouhými čísly. Máte někdo představu, jak jsou tam ta čísla implementována, popř., jak se tam s nima pracuje?
Je tamější definovaná struktura jiná, složitější?
Záleží na jazyku, v němž je to psáno?
A nebo postup, který jsem tady výše ohledně práce s dlouhými čísly popsal, už není možné nijak výrazněji vylepšit..

Díky za radu.

Vicemene jsi to trefil, jenom se pouziva pole misto spojaku a prvky nejsou cifry, ale inty. Takto to je v implementaci v .NET a GNU MP, jinde nevim, ale nejspis to bude uplne stejne.
Proc pole misto spojaku? Rychlejsi pristup ke vsem cifram, minimalni overhead.
Proc po velkych kusech a ne po cifrach? Procesor stejne bude pracovat s 32bit/64bit cislem, tak proc toho nevyuzit.
Jestli je struktura nejak slozitejsi. Treba v .NET se uklada opravdu jenom pole intu a par drobnosti.

Zajímavé. Napadá mě přitom ještě několik věcí:
Jednak, moje programátorské schopnosti zatím povětšinou tvoří Pascal a tam jsem naučený, že něco jako dynamicky alokované pole, pokud tam vůbec existuje, tak není nic samozřejmého. Takže jsem se vlastně polím v Pascalu dosud vyhýbal a věnoval se spíš spojovým seznamům. Přece jen, pokud bych načítal číslo předem neznámé délky, tak mi statické pole příjde dost nevhodné už z důvodu plýtvání místem..
V C++ apod. jsem viděl, že si můžu velikost pole celkem jednoduše volit až za běhu, takže popřemýšlím, v čem to nakonec budu psát.

K těm "pro pole" argumentům - pojem overhead neznám :(
A o té výhodě pole přistupovat rychleji ke všem cifrám jsem věděl, ale když jsem přemýšlel o těch několika procedurách, které jsem pro správu spojových seznamů už napsal, tak mi přišlo, že jsem právě snad ani nikde nepotřeboval přistupovat skokově k nějaké cifře a když jsem do spojového seznamu vstoupil, tak jsem jej snad vždycky potřeboval projít plynule od začátku do konce. Ať už to byly třeba funkce na základní aritmetické operace.. To, jestli to má využití později, zatím nevím.

Ještě mě napadlo, jestli může mít smysl pracovat v jiné než desítkové soustavě (ale o tom nevím, to jen tak hádám), protože například některé operace v dvojkové soustavě jsou tam někde hluboko zadrátované, tak by to v rámci časové optimalizace mohlo mít smysl..

A dík za tip s těmi číselnými úseky (inty místo cifer), zní to zajímavě. Musím si vyzkoušet, jak budu muset přizpsobit ty procedury tak, aby pracovaly s inty..

To Jeyekomon : Pokud to budeš mít v poli (a ideálně zarovnaném na 16bitovou hranici), dá se s výhodou využít MMX/SSE, takže určitě bych volil pole :-)

To Jeyekomon : I v pascalu je dynamicke alokovani, myslim ze se to jmenovalo getmem a freemem.
Overhead je pojem pro zbytecne operace/data. Teda ty, ktere nejsou primo pouzivane pro vypocet, ale jenom pomahaji vypoctu spravne fungovat. (toto jsem ted vysvetlil asi hodne spatne). Proste kdyz si koupis treba sesit, tak mas treba 20 listu, kam muzes psat+ 2 listy obal. Ty se nedaji vyuzit,jsou vlastne uplne k nicemu, ale jsou dobre na to, aby jsi tam napsaj treba jmeno, chrani ty listy uvnitr a tak. Toto je ten overhead potrebny ke sprave. A u spojaku jsou to ty zbytecne pointery, ktere ti usnadni praci, ale jsou pro to samotne ukladani dat nanic.
Pristup skokove k nejake cifre: Treba vsecky rychlejsi algoritny pro nasobeni (dokonce i deleni) pouzivaji nesekvencni pristup. Ale bezne "skolni" nasobeni ti bude urcite stacit.

Jak v Pascalu alokovat a používat dynamické pole už jsem tu jednou popisoval: http://programujte.com/?akce=diskuze&kam=vlakno&tema=16815-dvojrozmerne-pole#134557

Binární "cifry" čísla doporučuji ukládat bez znaménka, tj. ne integer nebo longint, ale word nebo dword. Znaménko může jít zvlášť třeba do nějakého booleanu.

Procesor má instrukce na počítání s binárními čísly a přičtení nebo odečtení přeteklé jedničky pro něj není problém. Přetečení přes desítku by se muselo počítat softwarově.
Příklad: mám dvě dlouhá čísla vyjádřená jako pole wordů v malém endianu (nejnižší je na začátku) a chci je sečíst (a:=a+b). V Asm to může vypadat třeba takhle:

les DI,a

lds SI,b

mov CX,pocet_wordu_v_cislech

add AX,0 {neco na vynulovani CF (nejspis existuje i nejaka vhodnejsi instrukce, ale zrovna si ji nepamatuju)}



 @cyklus:

 lodsw {do AX nacti jeden word pricitaneho cisla b a posun se za nej}

 adc AX,[ES:DI] {pricti word z cisla a, plus pripadnou preteklou jednicku z minule iterace}

 stosw {uloz vysledek do a a posun se v nem o word dal}

 loop @cyklus {opakuj pro kazdy word tech dvou cisel}



jnc @OK

 pretekl ten uplne nejvyssi bit, nahlas chybu (cisla bude potreba prodlouzit)

@OK:

Ten asm dneska už fungovat nebude, chtělo by ho to přepsat na 32 bitů… A ax není inicializovaný, je třeba ho vynulovat, třeba přes xor ax,ax.