/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
et lille problem ved manuel division
Fra : Janus Olsen


Dato : 20-05-04 09:42

At dividere manuelt på papir er nemt nok for mindre tal, men hvad med større
tal?
Skal jeg dividere 15654612 med 5465125, så skal jeg se om 5465128 går op i 1
hvad det ikke gør. Så teste mod 15, derefter 1565 ect til jeg skal teste om
5465128 går op i 1565461, hvad det stadig ikke gør, og til slut må jeg se
om 5465128 går op i 15654612 hvad det gør, men det er det oprindelige
divisionsstykke.

Man kan jo normalt dele sådan ... 5512 / 12 . man tester 5 div 12 hvilket
ikke giver >=1 og så 55 div 12 hvilket giver >=1. ser at 55 div 12=4.
derefter trækker man 12*4 fra de 55 og rykker ned så man får 712 og delvist
resultat 4. ect ect. I kender metoden.

Problemet er altså bare at hvis divisoren er så stor at den er uhåndterlig.
Det må da også være et problem for computere, hvis de ikke kan overskue hele
tallet på een gang? Har de fleste computere ikke et maksimum ved 4
milliarder? Jeg har testst og ser at man tilsyneladende kan bruge starten af
divisoren og starten af dividenden, men det giver alternative også fejl.
Måske et skridt den rette vej, men ikke helt nok.
Forsøg på at bryde divisionen ned til mindre del regnestykker fejler
desværre for mig.

Hvordan gør man egentlig?




 
 
Jeppe Stig Nielsen (20-05-2004)
Kommentar
Fra : Jeppe Stig Nielsen


Dato : 20-05-04 11:10

Janus Olsen wrote:
>
> At dividere manuelt på papir er nemt nok for mindre tal, men hvad med større
> tal?
> Skal jeg dividere 15654612 med 5465125, så skal jeg se om 5465128 går op i 1
> hvad det ikke gør. Så teste mod 15, derefter 1565 ect til jeg skal teste om
> 5465128 går op i 1565461, hvad det stadig ikke gør, og til slut må jeg se
> om 5465128 går op i 15654612 hvad det gør, men det er det oprindelige
> divisionsstykke.

Så ser du hvor mange gange (som helt tal!) 5465128 går op i 15654612.
Det er 2 gange. Så skriver du 2. Du regner 2×5465128 ud, det giver
10930256. Så trækker du dette tal fra de 15654612, så får du din rest
som er på 4724356. Så skal du føre det næste ciffer fra din dividend
ned, men da alle cifre allerede er opbrugt, tilføjer du »komma nul«
til dividenden (som er 15654612,00000...) og fører et 0 ned. Du sætter
kommaet efter dit 2-tal (i kvotienten). Med det nye nul står du med
tallet 47243560. Du ser hvor mange gange divisoren 5465128 går op. Det
gør den 8 gange. Så skriver du 8, etc.etc.

Resultatet bliver derfor 2,8...

Med tålmodighed skulle man gerne få 2,8644563482079549873...

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

Ole Andersen (20-05-2004)
Kommentar
Fra : Ole Andersen


Dato : 20-05-04 11:40

Jeppe Stig Nielsen wrote:

> Så ser du hvor mange gange (som helt tal!) 5465128 går op i 15654612.
> Det er 2 gange. ...

Og skulle man nu komme til at skønne galt, vil man opdage det, når
resten er mindre end nul eller større end divisoren.

--
Ole Andersen, Copenhagen, Denmark * http://palnatoke.org
Thesis #95: We are waking up and linking to each other. We are
watching. But we are not waiting. - Cluetrain Manifesto

Bertel Lund Hansen (20-05-2004)
Kommentar
Fra : Bertel Lund Hansen


Dato : 20-05-04 11:52

Janus Olsen skrev:

>At dividere manuelt på papir er nemt nok for mindre tal, men hvad med større
>tal?

Så laver man sig en tabel med gangestykkerne op til 9 gange
divisor og lægger ved siden af.

>Skal jeg dividere 15654612 med 5465125, så skal jeg se om 5465128 går op i 1
>hvad det ikke gør. Så teste mod 15, derefter 1565

Nu beskriver du det mere bøvlet end det reelt er. Man starter med
at tage nok cifre til at kunne komme i gang.

>Problemet er altså bare at hvis divisoren er så stor at den er uhåndterlig.

Nej, det er den nu ikke.

>Det må da også være et problem for computere, hvis de ikke kan overskue hele
>tallet på een gang?

Computere har generelt ingen som helst problemer.

>Har de fleste computere ikke et maksimum ved 4 milliarder?

En computers maksimum er begrænset af den samlede størrelse af
det virtuelle arbejdslager og rummer altså muligheder for at
arbejde med tal med milliarder af cifre. Men det er rigtigt at
mange implementationer af compilere til pc'er har en normal
heltalstype der maksimalt kan være ca. 2 mia. med fortegn og 4
uden. Det behøver et program dog ikke lade sig slå ud af. Jeg har
lavet rutiner med store tal hvor jeg slog så mange heltal sammen
som jeg skulle bruge - altså faktisk regnede med et
4-milliardtals-system (eler rettere et 65536-tals-system.
Gangestykker fylder jo det dobbelte).

>Forsøg på at bryde divisionen ned til mindre del regnestykker fejler
>desværre for mig.

Jeg ved ikke hvordan divisioner er implementeret i diverse
programmeringssprog eller for den sags skyld i mikrokoden, men
man kan i hvert fald bruge den algoritme som man også bruger i
hånden. Den er nu nok bare for langsom, men den virker:

>Hvordan gør man egentlig?

Med en 5465125-tabel ved siden af er det ikke spor svært at lave
lange divisioner i hånden med det tal.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

Martin Larsen (20-05-2004)
Kommentar
Fra : Martin Larsen


Dato : 20-05-04 12:03

"Bertel Lund Hansen" <nospamius@lundhansen.dk> skrev i en meddelelse news:3o2pa0hvheu0sl3n2b1mpstda2m3kfb49l@news.stofanet.dk...
> Janus Olsen skrev:
>
> >At dividere manuelt på papir er nemt nok for mindre tal, men hvad med større
> >tal?
>
> Så laver man sig en tabel med gangestykkerne op til 9 gange
> divisor og lægger ved siden af.
>
> >Skal jeg dividere 15654612 med 5465125, så skal jeg se om 5465128 går op i 1
> >hvad det ikke gør. Så teste mod 15, derefter 1565
>
> Nu beskriver du det mere bøvlet end det reelt er. Man starter med
> at tage nok cifre til at kunne komme i gang.
>
> >Problemet er altså bare at hvis divisoren er så stor at den er uhåndterlig.
>
> Nej, det er den nu ikke.
>
> >Det må da også være et problem for computere, hvis de ikke kan overskue hele
> >tallet på een gang?
>
> Computere har generelt ingen som helst problemer.
>
> >Har de fleste computere ikke et maksimum ved 4 milliarder?
>
> En computers maksimum er begrænset af den samlede størrelse af
> det virtuelle arbejdslager

Nej, i princippet kan PC'en spytte cifre ud i en lind strøm.

Mvh
Martin



Bertel Lund Hansen (20-05-2004)
Kommentar
Fra : Bertel Lund Hansen


Dato : 20-05-04 12:26

Martin Larsen skrev:

>Nej, i princippet kan PC'en spytte cifre ud i en lind strøm.

Jo, hvis cifrene er ligegyldige. Hvis de skal være resultatet af
en korrekt beregning, er computeren nødt til at lagre de
nødvendige tal på en eller anden måde, så der vil være en grænse.

Der findes muligvis snedige måder at gøre det på så den måske kan
pakke tallene og kun udpakke en lille del der skal regnes på, men
den slags tricks flytter kun grænsen. Det fjerner den ikke.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

Martin Larsen (20-05-2004)
Kommentar
Fra : Martin Larsen


Dato : 20-05-04 13:08

"Bertel Lund Hansen" <nospamius@lundhansen.dk> skrev i en meddelelse news:d95pa013mong860upuor56jp82b4f84v94@news.stofanet.dk...
> Martin Larsen skrev:
>
> >Nej, i princippet kan PC'en spytte cifre ud i en lind strøm.
>
> computeren nødt til at lagre de
> nødvendige tal på en eller anden måde, så der vil være en grænse.

Dine tautologiske korrektheder vil jeg ikke kommentere (yderligere)

Mvh
Martin



Henrik Christian Gro~ (20-05-2004)
Kommentar
Fra : Henrik Christian Gro~


Dato : 20-05-04 13:43

Bertel Lund Hansen <nospamius@lundhansen.dk> writes:

> Martin Larsen skrev:
>
> >Nej, i princippet kan PC'en spytte cifre ud i en lind strøm.
>
> Jo, hvis cifrene er ligegyldige. Hvis de skal være resultatet af
> en korrekt beregning, er computeren nødt til at lagre de
> nødvendige tal på en eller anden måde, så der vil være en grænse.

Ja, men de nødvendige tal behøver ikke fylde ret meget.

Hvis vi f.eks. tager det regnestykke der startede denne diskussion, så
er det eneste vi behøver huske divisoren 5465125 og den seneste rest, vi
skal hverken bruge alle de decimaler vi har spyttet ud eller alle
mellemregningerne, så der er reelt ingen grænse for hvor mange decimaler
vi kan få maskinen til at spytte ud som resultat af den
beregning.

..Henrik

--
Det er da osse helt urimeligt at et saa udbredt topologisk rum som Q
ikke er lokalkompakt.               -- Stefan Holm

Bertel Lund Hansen (20-05-2004)
Kommentar
Fra : Bertel Lund Hansen


Dato : 20-05-04 15:22

Henrik Christian Grove skrev:

>Hvis vi f.eks. tager det regnestykke der startede denne diskussion, så
>er det eneste vi behøver huske divisoren 5465125 og den seneste rest, vi
>skal hverken bruge alle de decimaler vi har spyttet ud eller alle
>mellemregningerne, så der er reelt ingen grænse for hvor mange decimaler
>vi kan få maskinen til at spytte ud som resultat af den
>beregning.

Det er ganske rigtigt.

Jeg svarede på et spørgsmål om der var en grænse ved 4 mia.
(svarende til 4 byte), og derfor tænkte jeg på at der er en
grænse for hvor store tal computeren kan arbejde med. Der vil
f.eks. være en grænse for hvor store tal den kan dividere med.

Indenfor de tal som den kan håndtere, er der så mange resultater
der vil kunne afleveres med ubegrænset præcision.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

Henning Makholm (20-05-2004)
Kommentar
Fra : Henning Makholm


Dato : 20-05-04 16:26

Scripsit Bertel Lund Hansen <nospamius@lundhansen.dk>

> Så laver man sig en tabel med gangestykkerne op til 9 gange
> divisor og lægger ved siden af.
.....
> >Det må da også være et problem for computere, hvis de ikke kan overskue hele
> >tallet på een gang?

> Computere har generelt ingen som helst problemer.

Nej, for de regner jo binært. Så skal man starte med at lave sig en
tabel med gangestykkerne op til 1 gange divisor, og det er jo til at
overskue.

> Jeg ved ikke hvordan divisioner er implementeret i diverse
> programmeringssprog eller for den sags skyld i mikrokoden, men
> man kan i hvert fald bruge den algoritme som man også bruger i
> hånden. Den er nu nok bare for langsom, men den virker:

Jeg tvivler på at det i det generelle tilfælde kan gøres meget
hurtigere end håndregningsalgoritmen. (Man kan naturligvis skrue på
hvor mange bits ad gangen man tager, men det kan næppe betale sig med
mindre man enten implementerer skidtet i hardware og har rigtig mange
transistorer til overs, eller tallene er større end man kan trække fra
hinanden på én gang).

--
Henning Makholm "... not one has been remembered from the time
when the author studied freshman physics. Quite the
contrary: he merely remembers that such and such is true, and to
explain it he invents a demonstration at the moment it is needed."

Jens Axel Søgaard (20-05-2004)
Kommentar
Fra : Jens Axel Søgaard


Dato : 20-05-04 20:16

Henning Makholm wrote:

> Jeg tvivler på at det i det generelle tilfælde kan gøres meget
> hurtigere end håndregningsalgoritmen.

Det første skridt, hvor man finder kvotient og rest ved
heltalsdivision kan speedes lidt ved at benytte Newton-iteration.
Med den metode kan heltalsdivision med rest udføres med
samme asympotiske tidsforbrug som multiplikation.

Men om det på snedig vis kan udnyttes til at forbedre
tidsforbruget ved håndregningsalgoritmen kan jeg ikke
gennemskue.

--
Jens Axel Søgaard

Henning Makholm (20-05-2004)
Kommentar
Fra : Henning Makholm


Dato : 20-05-04 22:48

Scripsit Jens Axel Søgaard <usenet@soegaard.net>
> Henning Makholm wrote:

> > Jeg tvivler på at det i det generelle tilfælde kan gøres meget
> > hurtigere end håndregningsalgoritmen.

> Det første skridt, hvor man finder kvotient og rest ved
> heltalsdivision kan speedes lidt ved at benytte Newton-iteration.

Hvordan? Newton-iteration indeholder jo selv divisioner.

Hvilken funktion vil du bruge Newton-iteration på? Hvis du bruger den
naturlige definition

xa-1=0

vil første skridt af iterationen jo reducere til at finde x=1/a
præcist.

--
Henning Makholm "The trouble is that the chapter is entirely
impenetrable. Its message is concealed behind not just
thickets of formalism, but hedges, woods, and forests of
formalism. There are whole pages with not even a paragraph break."

Jens Axel Søgaard (21-05-2004)
Kommentar
Fra : Jens Axel Søgaard


Dato : 21-05-04 00:11

Henning Makholm wrote:

> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
>>Henning Makholm wrote:

>>>Jeg tvivler på at det i det generelle tilfælde kan gøres meget
>>>hurtigere end håndregningsalgoritmen.

>>Det første skridt, hvor man finder kvotient og rest ved
>>heltalsdivision kan speedes lidt ved at benytte Newton-iteration.

> Hvordan? Newton-iteration indeholder jo selv divisioner.
>
> Hvilken funktion vil du bruge Newton-iteration på? Hvis du bruger den
> naturlige definition
>
> xa-1=0
>
> vil første skridt af iterationen jo reducere til at finde x=1/a
> præcist.

Har du et eksemplar af Knuth i nærheden? Det er algoritme R
i afsnit 4.3.3 i vol 2.

I korte træk (det er sent - jeg kan overtales til at uddybe
i morgen):

- problemet med at dividere et n-bit tal u
med et n-bit tal v kan reduceres til at
at finde en n-bits-approksimation af 1/v

- 1/v kan findes ved Newton-iteration:

x0 er "tæt på" 1/v

x_n+1 = 2 x_n - v (x_n)^2

Hvis (vi kalder lige epsilon for e)

x_n = (1-e)/v

så er

x_n+1 = (1-e^2)/v

Eksempel:

> (define v 1/3)
> (define (next x)
(- (* 2 x) (* v x x)))
> (define (f n x) ; newton iteration n gange på x
(if (= n 0)
x
(f (- n 1) (next x))))
> (f 0 1)
1
> (f 1 1)
1 2/3
> (f 2 1)
2 11/27
> (f 3 1)
2 1931/2187
> (f 4 1)
2 14283371/14348907
> (f 5 1)
2 617669101316651/617673396283947
> (f 6 1)
2 1144561273412390750812240144811
/1144561273430837494885949696427
> (f 7 1)
2 3930061525912861057173284004770585283429273822817848601487531
/3930061525912861057173624287137506221892737197425280369698987

> (f 0 1.0)
1.0
> (f 2 1.0)
2.4074074074074074
> (f 3 1.0)
2.88294467306813
> (f 4 1.0)
2.9954326834789575
> (f 5 1.0)
2.9999930465399323
> (f 6 1.0)
2.999999999983883
> (f 7 1.0)
3.0

--
Jens Axel Søgaard

Henning Makholm (21-05-2004)
Kommentar
Fra : Henning Makholm


Dato : 21-05-04 01:28

Scripsit Jens Axel Søgaard <usenet@soegaard.net>
> Henning Makholm wrote:

> > Hvordan? Newton-iteration indeholder jo selv divisioner.

> Har du et eksemplar af Knuth i nærheden?

Kun bind 3.

> - 1/v kan findes ved Newton-iteration:

> x_n+1 = 2 x_n - v (x_n)^2

Aha .. ved rodfinding i funktionen

x |-> v-1/x

går divisionerne ud mod hinanden. Smart. Men man skal sørge for at
x0 er lille nok - hvis den er mere end 2 gange den ægte værdi af
1/v, divergerer iterationen mod -uendelig. Nå, det kan man forholdsvis
nemt undgå ved at tælle bits.

Så vidt jeg kan se, vinder man imidlertid kun noget, hvis man kan
multiplicere tal væsentlig hurtigere end den almindelige kvadraiske
divisionsalgoritme. Det findes der vistnok algoritmer til, men de er
så vidt jeg husker kun en gevinst hvis der er rigtig mange bits. Og
jeg har aldrig hørt om nogen der brugte dem til papirudregninger.

Hvis nævneren holdes konstant, nytter iterationen ihvertfald ikke
noget når antallet af uddatacifre går mod uendeligt - så kan
papirmetoden producere n bits af resultatet i tid O(n), mens den
iterative metode skal bruge O(n logn loglogn) eller mere blot til den
sidste kvadrering i multiplikationen.

> > (f 7 1)

> 2 3930061525912861057173284004770585283429273822817848601487531
> /3930061525912861057173624287137506221892737197425280369698987

Det virker lidt som en omvej at udregne rationelle approksimationer
til en eksakt brøk.

--
Henning Makholm "No one seems to know what
distinguishes a bell from a whistle."

Jens Axel Søgaard (21-05-2004)
Kommentar
Fra : Jens Axel Søgaard


Dato : 21-05-04 14:09

Henning Makholm wrote:
> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
>
>>Henning Makholm wrote:

>>>Hvordan? Newton-iteration indeholder jo selv divisioner.

>>Har du et eksemplar af Knuth i nærheden?

> Kun bind 3.

Så skriver jeg lige af:


Algorithm R (High-precision reciprocal)
---------------------------------------

Let v have the binary representation
v=(0.v v v v ... ) where v = 1.
1 2 3 2 1
This algorithm computes an approximation z
to 1/v such that
-n
| z - 1/v | <= 2

R1. [Initial approximation]
Set

z <- 1/4 floor( 32 / ( 4v + 2v + v ) )
1 2 3
and k <- 0.

R2. [Newtonian iteration]
(At this point we have a number z of the binary
form (xx.xx...x) with 2^k + 1 places after the radix
2
point, and z<=2.)

2
Calculate z = (xxx.xx...x) exactly, using a high-speed
2 2
multiplication routine. Then calculate V z exactly,
k
where V = (0.v v ... v ) .
k 1 2 2^(k+1)+2 2
k+1
2 -2 - 1
Then set z <- 2z - V z + r , where 0<= r < 2 .
k

Finally, set k <- k +1.

R3. [Test for end]
k
If 2 < n go back to step R2; otherwise the algorithm
terminates.

Knuth fortsætter med at en variant af denne teknik er
blevet brugt i computerhardware (referencen er fra 1967).

Han viser at tidsforbruget er < T(8n) hvor T(n) er
tiden det tager at multiplicere to n-bit-tal.


>> - 1/v kan findes ved Newton-iteration:
>
>
>> x_n+1 = 2 x_n - v (x_n)^2
>
>
> Aha .. ved rodfinding i funktionen
>
> x |-> v-1/x
>
> går divisionerne ud mod hinanden. Smart.

Det er mest almindeligt at anvende teknikken, ved udregning
polynomiumsringe over en variabel. Hvor tingene er nemmere
at have med at gøre end når man regner på gemene tal.

> Men man skal sørge for at
> x0 er lille nok - hvis den er mere end 2 gange den ægte værdi af
> 1/v, divergerer iterationen mod -uendelig. Nå, det kan man forholdsvis
> nemt undgå ved at tælle bits.

Man kan se af R1 at det er nok at se på de første tre bits.

> Så vidt jeg kan se, vinder man imidlertid kun noget, hvis man kan
> multiplicere tal væsentlig hurtigere end den almindelige kvadraiske
> divisionsalgoritme. Det findes der vistnok algoritmer til, men de er
> så vidt jeg husker kun en gevinst hvis der er rigtig mange bits.

Ja - ovenstående har kun praktisk interesse, hvis man regner
på meget store tal.

> Og jeg har aldrig hørt om nogen der brugte dem til papirudregninger.

Heller ikke her, men Jonas og Bertel drejede jo også tråden
over til computerberegninger.

> Hvis nævneren holdes konstant, nytter iterationen ihvertfald ikke
> noget når antallet af uddatacifre går mod uendeligt - så kan
> papirmetoden producere n bits af resultatet i tid O(n), mens den
> iterative metode skal bruge O(n logn loglogn) eller mere blot til den
> sidste kvadrering i multiplikationen.

Det kan jeg ikke lige gennemskue.


>> > (f 7 1)

>>2 3930061525912861057173284004770585283429273822817848601487531
>> /3930061525912861057173624287137506221892737197425280369698987

> Det virker lidt som en omvej at udregne rationelle approksimationer
> til en eksakt brøk.

Heh. Det var mest fordi jeg blev så forbløffet over at få
tallene eksakt, at jeg syntes det var sjovt at tage dem med.


--
Jens Axel Søgaard

Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408849
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste