Kehrwert von Hand berechnen
Lukas-Fabian Moser
gibt es zum schriftlichen Berechnen des Kehrwertes einer natürlichen
Zahl eine bessere Methode als "normale" schriftliche Division?
Lukas
Helmut Richter
>gibt es zum schriftlichen Berechnen des Kehrwertes einer natürlichen
>Zahl eine bessere Methode als "normale" schriftliche Division?
Wie soll das Ergebnis aussehen? Dezimalbruch? Äquivalent mit anderer
Basis?
Und was heißt "schriftlich"? Ohne Rechner mit Bleistift und Papier?
Falls ohne Rechner, denke ich, dass die "normale" schriftliche
Division gar nicht so schlecht ist. Falls mit Rechner, wird man wohl
eher auf ganze Zahlen umsteigen, weil es dafür Programme gibt, für
periodische Dezimalbrüche m.W. aber viel weniger. Beispiel: 1/51613
als Dezimalbruch mit "maple". (Ich hab keine Ahnung, ob "maple" auch
mit Dezimalbrüchen rechnen könnte. Der folgende Weg ist der
einfachste, falls nein. Es wird kein Programm geschrieben, sondern nur
interaktiv Ergebnisse abgefragt.)
Erst mal n-1 zerlegen:
> ifactor (51612);
2
(2) (3) (11) (17) (23)
Dann Periodenlänge feststellen (wie weit kann man 51612 dividieren, so
dass 10^x mod 51613 immer noch 1 ist?):
> 10 &^ (51612/2) mod 51613;
1
> 10 &^ (51612/4) mod 51613;
1
> 10 &^ (51612/12) mod 51613;
9742
> 10 &^ (51612/44) mod 51613;
16924
> 10 &^ (51612/68) mod 51613;
21978
> 10 &^ (51612/92) mod 51613;
1
Die Periodenlänge ist also 51612/92 = 561.
Jetzt die Periode selbst. Sie ist (10^561-1)/51613, mit führenden
Nullen auf 561 Stellen ergänzt:
> (10^561-1)/51613;
193749636719431151066591750140468486621587584523279018851839652800650998779\
37728866758374828047197411504853428399821750334218123341018735589870768\
99230813942223858330265630751942340108112297289442582295158196578381415\
53484587216398969251932652626276325731889252707651173154050336155619708\
21304710053668649371282428845445914788909770794179760912948288221959583\
82578032666188750896092069827369073682986844399666750624842578420165462\
18975839420301086935461996008757483579718288028209947106349175595295758\
82045221165210315230658942514482785344777478542227733323
Mehr dazu in http://www.lrz-muenchen.de/~hr/numb/period.html .
Helmut Richter
Hermann Kremer
Lukas-Fabian Moser schrieb in Nachricht <3b52db8f...@news.lrz-muenchen.de>...
>Hallo,
>
>gibt es zum schriftlichen Berechnen des Kehrwertes einer natürlichen
>Zahl eine bessere Methode als "normale" schriftliche Division?
Hallo Lukas,
wie wäre es denn mit der Entwicklung in einen "ägyptischen Bruch" (egyptian
fraction: Summe von Stammbrüchen): 1/7 = 1/8 + 1/56 ?
Das läuft unter dem Stichwort Farey-Entwicklung:
http://www.ics.uci.edu/~eppstein/numth/egypt
und ist auch mathematikhistorisch äußerst interessant (Rechenbuch des Ahmes = Papyrus
Rhind ...)
Grüße
Hermann
--
>
>Lukas
Rainer Rosenthal
Hermann Kremer griff in die Link-Kiste:
> wie wäre es denn mit der Entwicklung in einen "ägyptischen Bruch"
> (egyptian fraction: Summe von Stammbrüchen): 1/7=1/8+1/56 ?
> Das läuft unter dem Stichwort Farey-Entwicklung:
> http://www.ics.uci.edu/~eppstein/numth/egypt
> und ist auch mathematikhistorisch äußerst interessant (Rechenbuch
> des Ahmes = Papyrus Rhind ...)
>
Hallo Hermann, hallo Lukas,
Aus meiner Link-Sammlung:
Eine Übersicht inklusive Landkarte:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html
Aus der von Dir genannten Referenz habe ich speziell folgendes zu
empfehlen:
http://www.ics.uci.edu/~eppstein/numth/egypt/odd-one.html
( Diskussion über Darstellung der 1 als Summe von Reziproken
verschiedener ungerader Zahlen, d.h. ägyptischer Brüche mit
ungeradem Nenner. Wesentliche Beiträge von Fred. W. Helenius
Greedy algorithm, abundant numbers, pseudo-perfect numbers,
weird numbers )
Hier schon etwas herberes , d.h. da wird einiges gerechnet, aber es
ist mir zu mühsam, das nachzuvollziehen. Wenn Du, Lukas, das tust
und was interessantes zu berichten weisst, dann wäre das schön.
http://www-history.mcs.st-and.ac.uk/~history/HistTopics/Egyptian_papyri.html
Bei der Suche in meinen Links hat sich der Ägyptische Flughund
eingeschlichen. Na gut, also setze ich diesen netten Link auch hierher:
http://www.das-tierlexikon.de/flughunde.htm
Hier ein Java Applet mit Ägyptischen Bruchdarstellungen. Ich habe z.B.
eingetippt die Zahlen 5 und 8 und die Schreibtafel zeigt mir als
"best solution so far" an: 5/8 = 1/2 + 1/8.
http://www.christs.cam.ac.uk/bio/programs/egyptian-fractions/example-a.html
Gruss,
Rainer
Jürgen Böhm
Es gibt tatsächlich andere Methoden, sogar für allgemeine reelle Zahlen
und sie haben sogar eine technische Bedeutung, nämlich als Algorithmen
für die floating-point Arithmetik in den Rechenwerken von
Digitalrechnern.
Einzelheiten siehe:
D.E.Knuth, The Art of Computer Programming, Vol II,
im Abschnitt 4.3.1, Arithmetic, The Classical Algorithms
Am naheliegendsten ist die Verwendung des Newton-Verfahrens für die
Funktion
f(x) = 1/x - a
f(x0)=0 => x0 = 1/a
Setzt man wie üblich an
x(n+1) = x(n) - f(x(n))/f'(x(n))
ergibt sich
x(n+1) = x(n) * (2-a*x(n))
mit quadratischer Konvergenz (Anzahl der gültigen Stellen verdoppelt
sich mit jedem Schritt).
Knuth gibt an obiger Stelle auch noch eine iterative Formel mit
kubischer Konvergenz an und verweist auf die Literatur für ein Verfahren
4. Ordnung.
(das obige habe ich so runtergeschrieben, dann fiel mir erst auf, dass
Du ja "natürliche Zahl" gesagt hattest. Leider kann ich Dir jetzt keine
besonders hübschen Algorithmen für diese Division liefern, die sich
vielleicht auf irgendwelche zahlentheoretischen Eigenschaften beziehen.
Dennoch dürfte es hier (auch über die ägyptischen Brüche hinaus) noch
einiges geben - irgendwann habe ich mal gelesen, dass Gauss das
quadratische Reziprozitätsgesetz experimentell entdeckt hat, indem er
die Dezimalbruchentwicklung der Kehrwerte der Primzahlen 1/p mit p < 100
oder 1000 ausrechnete...vielleicht weiss ja jemand mehr dazu ?)
MfG
Jürgen Böhm
-----------------------------------------------------------------------
Dipl.-Math. Jürgen Böhm http://www.aviduratas.de
"At a time when so many scholars are calculating, is it not desirable,
that some, who can, dream ?" R. Thom
Hermann Kremer
Rainer Rosenthal schrieb in Nachricht <9ivk7r$l7b1h$1...@ID-54909.news.dfncis.de>...
>
>Hermann Kremer griff in die Link-Kiste:
>
>> wie wäre es denn mit der Entwicklung in einen "ägyptischen Bruch"
>> (egyptian fraction: Summe von Stammbrüchen): 1/7=1/8+1/56 ?
>> Das läuft unter dem Stichwort Farey-Entwicklung:
>> http://www.ics.uci.edu/~eppstein/numth/egypt
>> und ist auch mathematikhistorisch äußerst interessant (Rechenbuch
>> des Ahmes = Papyrus Rhind ...)
>>
Hallo Rainer, hallo Lukas,
>Aus meiner Link-Sammlung:
>Eine Übersicht inklusive Landkarte:
>http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html
>
>Aus der von Dir genannten Referenz habe ich speziell folgendes zu
>empfehlen:
>http://www.ics.uci.edu/~eppstein/numth/egypt/odd-one.html
>( Diskussion über Darstellung der 1 als Summe von Reziproken
> verschiedener ungerader Zahlen, d.h. ägyptischer Brüche mit
> ungeradem Nenner. Wesentliche Beiträge von Fred. W. Helenius
> Greedy algorithm, abundant numbers, pseudo-perfect numbers,
> weird numbers )
>
>Hier schon etwas herberes , d.h. da wird einiges gerechnet, aber es
>ist mir zu mühsam, das nachzuvollziehen. Wenn Du, Lukas, das tust
>und was interessantes zu berichten weisst, dann wäre das schön.
>http://www-history.mcs.st-and.ac.uk/~history/HistTopics/Egyptian_papyri.html
>
>
>Bei der Suche in meinen Links hat sich der Ägyptische Flughund
>eingeschlichen. Na gut, also setze ich diesen netten Link auch hierher:
>http://www.das-tierlexikon.de/flughunde.htm
Dieses Lexikon ist übrigens ganz hervorragend ... (fast) ein zoologisches
Pendant zu dem jetzt ja wohl zwangsweise ge-crashed-ten
http://br.crashed.net/~akrowne/crc/math0 ;-((
>Hier ein Java Applet mit Ägyptischen Bruchdarstellungen. Ich habe z.B.
>eingetippt die Zahlen 5 und 8 und die Schreibtafel zeigt mir als
>"best solution so far" an: 5/8 = 1/2 + 1/8.
>http://www.christs.cam.ac.uk/bio/programs/egyptian-fractions/example-a.html
Ja, und das Applet liefert:
321/997 = 1/4 + 1/14 + 1/1994 + 1/27916
während mein eigenes Greedy-Programm dafür
321/997 = 1/4 + 1/14 + 1/1862 + 1/3712828
liefert ...
BTW:
Ein Experte bezüglich der altägyptischen Historie von Einheitsbrüchen ist
übrigens der Krypt-Analytiker Milo Gardner (... bekannt aus sci.math ...).
Es gibt auch eine recht hübsche Spezialpage von Bruce Friedman über
altägyptische Mathematik:
http://hometown.aol.com/brucefriedmandcg/index.html
Eine ebenfalls sehenswerte, aber etwas esot(h)erisch eingefärbte Seite ist
http://www.legon.demon.co.uk/index.htm
Und wenn Ihr mal mit Hieroglyphen-Ziffern rechnen wollt:
http://www.eyelid.co.uk/numbers.htm
Hmmm, ob ich jetzt wohl besser ein [OT - Hieroglyphen/Zoologie] ins
Subject schreiben sollte ?
Grüße
Hermann
--
>Gruss,
>Rainer
>
Lukas-Fabian Moser
On Mon, 16 Jul 2001 12:20:18 GMT, l...@gmx.de (Lukas-Fabian Moser)
wrote:
>gibt es zum schriftlichen Berechnen des Kehrwertes einer natürlichen
>Zahl eine bessere Methode als "normale" schriftliche Division?
Ich habe mir jetzt folgenden Algorithmus notiert, um einen Kehrwert
näherungsweise zu berechnen; er basiert, wie auch Jürgens Vorschlag,
auf dem Newtonverfahren. Sein Vorteil liegt darin, daß man nur einmal
subtrahieren und wenige Male multiplizieren muß.
Um den Kehrwert einer (natürlich) Zahl a zu bestimmen:
Suche eine möglichst kleine natürliche Zahl n, so daß n*a "möglichst
relativ nahe" bei einer Zehnerpotenz liegt, aber nicht größer ist als
diese. Bestimme dann m so, daß 1 < 10^(1-m) * n * a <= 10 ist. Dann
ist eine Näherung für 1/a gegeben durch n * (2 - 10^(-m) * n * a) *
10^(-m).
Ein Beispiel:
Wir suchen den Kehrwert von a = 8091 (an diesem Fall hatte sich mein
Interesse an der Frage "entzündet"). Man könnte entweder nun n = 1
setzen (und auch schon ein brauchbares Ergebnis erhalten), wir nehmen
aber n = 12. Es ist 12 * 8091 = 97092, dann nehmen wir m = 5 [diese
Bestimmung kann man sich, wenn man das Verfahren wirklich anwendet,
sparen und direkt den Faktor 0,00001 verwenden]. Damit ergibt sich die
Näherung 12 * (2 - 0.97092) * 0,00001 = 0,0001234896. Der wahre Wert
wäre 0,00012359411..., der Fehler beträgt also ca. 0.085%. Hätte man n
= 1 verwendet, bekäme man die Näherung 0,00011909 mit dem Fehler
3,644%.
Vermutlich gibt es bessere Verfahren, aber dieses ist zumindest schön
einfach.
Grüße, Lukas