Integer overflow - Aneb, když jsou vám trenky těsné – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Jeyekomon0
Stálý člen
2. 1. 2011   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 78.128.199.–
jjk
Reklama
Reklama
Krychlik
~ Anonymní uživatel
195 příspěvků
2. 1. 2011   #2
-
0
-

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.

Nahlásit jako SPAM
IP: 217.115.240.–
Jeyekomon0
Stálý člen
2. 1. 2011   #3
-
0
-

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..

Nahlásit jako SPAM
IP: 78.128.199.–
jjk
Michal Wiglasz
~ Anonymní uživatel
2 příspěvky
2. 1. 2011   #4
-
0
-

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 :-)

Nahlásit jako SPAM
IP: 147.229.206.–
Krychlik
~ Anonymní uživatel
195 příspěvků
3. 1. 2011   #5
-
0
-

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.

Nahlásit jako SPAM
IP: 217.115.240.–
Mircosoft+1
Věrný člen
4. 1. 2011   #6
-
0
-

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:


Na násobení existuje algoritmus, který se skládá jenom z bitových posunů a sčítání, takže pohoda. Dělení nevím, zkusím zapátrat.

Nahlásit jako SPAM
IP: 130.119.248.–
Chceš-li lepší odpověď, polož lepší otázku.
Moje stránka.
Michal Wiglasz
~ Anonymní uživatel
2 příspěvky
11. 1. 2011   #7
-
0
-

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.

Nahlásit jako SPAM
IP: 147.229.206.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 11 hostů

Podobná vlákna

Řetězec -> integer — založil Ondřej

Ifstream.get -> integer — založil Debugger

Overflow — založil kolarcz

Overflow — založil Johny.

Text-overflow — založil Onsi

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý