| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Namronia
1500+ mal Qualität!
Anmeldungsdatum: 23.01.2008
Beiträge: 1687
|
 (#1646531) Verfasst am: 07.06.2011, 11:19 Titel: Quersumme von 100! |
 |
|
Ich sitz hier gerade vor nem Problem:
Ich will die Quersumme von 100 Fakultät ausrechnen. Das Problem der meisten Programmiersprachen ist, dass man nicht einfach in nen Integer konvertieren kann, das Problem z.B. bei Perl und PHP ist, dass sie
9.33262154 × 10^157
speichern und damit lässt sich dann keine Quersumme berechnen.
Mit use Math::BigInt; gehts auch irgendwie nicht.
Wie kann ich das relativ schnell & einfach berechnen? Sprache wäre vorzugsweise Perl oder C++.
Edit: Ich glaub, ich habs gelöst. Stimmt das Ergebnis? 648?
Der Code wäre:
| Code: |
#!/usr/bin/perl
use Math::BigInt;
my $wert = Math::BigInt->new('100.0');
sub fac {
my ($n) = @_;
if ($n <2>new($wx);
my @array = split(//, $x);
my $a = 0;
foreach (@array) {
$a += $_;
}
print "\n\n$a\n\a";
|
|
|
| Nach oben |
|
 |
Ilmor
auf eigenen Wunsch deaktiviert
Anmeldungsdatum: 13.12.2008
Beiträge: 7151
|
| (#1646534) Verfasst am: 07.06.2011, 11:29 Titel: |
|
|
| 9.33262154 × 10^157 übertrifft den Wertebereich von Int und Long bei weitem. Du musst einen eigenen Datentypen programmieren, der eine solche Zahl als Ganzahl ausdrücken kann. Du könntest zB ein 157 Stellen langes Array Programmieren, das an jeder Stelle die Werte von 0 bis 9 annehmen kann. Dann musst du noch die Multiplikation auf diesen Array definieren.
|
|
| Nach oben |
|
|
Namronia
1500+ mal Qualität!
Anmeldungsdatum: 23.01.2008
Beiträge: 1687
|
| (#1646535) Verfasst am: 07.06.2011, 11:33 Titel: |
|
|
| Ilmor hat folgendes geschrieben: | | 9.33262154 × 10^157 übertrifft den Wertebereich von Int und Long bei weitem. Du musst einen eigenen Datentypen programmieren, der eine solche Zahl als Ganzahl ausdrücken kann. Du könntest zB ein 157 Stellen langes Array Programmieren, das an jeder Stelle die Werte von 0 bis 9 annehmen kann. Dann musst du noch die Multiplikation auf diesen Array definieren. |
Ja, das ist genau das Problem, an dem ich hing & ich weiß nicht, wie man eigene Datentypen in Perl definiert (wollte es aber gern in Perl machen).
Aber wie gesagt, ich denke, ich habe das Ding doch mit bigint lösen können.
Danke trotzdem.
|
|
| Nach oben |
|
|
esme
lebt ohne schützende Gänsefüßchen.
Anmeldungsdatum: 12.06.2005
Beiträge: 5667
|
| (#1646602) Verfasst am: 07.06.2011, 14:48 Titel: |
|
|
Warum willst du die Quersumme berechnen?
_________________
Gunkl über Intelligent Design:
Da hat sich die Kirche beim Rückzugsgefecht noch einmal grandios verstolpert und jetzt wollen sie auch noch Haltungsnoten für die argumentative Brez'n, die sie da gerissen haben.
|
|
| Nach oben |
|
|
Namronia
1500+ mal Qualität!
Anmeldungsdatum: 23.01.2008
Beiträge: 1687
|
| (#1646701) Verfasst am: 07.06.2011, 20:14 Titel: |
|
|
| esme hat folgendes geschrieben: | | Warum willst du die Quersumme berechnen? |
Wir haben gerade in der Berufsschule nicht all zu viel zu tun und wir haben Project Euler gefunden. Ne Seite, mit mathematischen Problemen, die man irgendwie durch Software lösen muss. Und eines davon war genau das hier, aber ich habs zum Glück geschafft 
|
|
| Nach oben |
|
|
nocquae
diskriminiert nazis
Anmeldungsdatum: 16.07.2003
Beiträge: 18183
|
| (#1646703) Verfasst am: 07.06.2011, 20:20 Titel: |
|
|
| Namronia hat folgendes geschrieben: | | esme hat folgendes geschrieben: | | Warum willst du die Quersumme berechnen? |
Wir haben gerade in der Berufsschule nicht all zu viel zu tun und wir haben Project Euler gefunden. Ne Seite, mit mathematischen Problemen, die man irgendwie durch Software lösen muss. Und eines davon war genau das hier, aber ich habs zum Glück geschafft |
Aber warum denn in Perl?
Da liegen doch nun wirklich nicht dessen Stärken.
Ich hab mal zur Übung ein Programm zur Primfaktorzerlegung einmal in C++ und einmal in Python geschrieben – Wo C++ noch ca. 30 min brauchte, lag Python schon bei ca. 4 Stunden.
Python wenn es einfach sein und funktionieren soll,
C++ wenn es zeitkritisch ist,
Perl wenn es um Reintext geht,
Java, wenn es langsam sein und nur sporadisch funktionieren soll.
_________________
In Deutschland gilt derjenige, der auf den Schmutz hinweist, als viel gefährlicher, als derjenige, der den Schmutz macht.
-- Kurt Tucholsky
|
|
| Nach oben |
|
|
DerBernd
auf Wunsch deaktiviert
Anmeldungsdatum: 16.10.2010
Beiträge: 1043
|
| (#1646716) Verfasst am: 07.06.2011, 21:11 Titel: Re: Quersumme von 100! |
|
|
| Namronia hat folgendes geschrieben: |
Edit: Ich glaub, ich habs gelöst. Stimmt das Ergebnis? 648?
|
Ja, das spuckt mein Taschenrechner auch aus, 100! ist 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ; die Quersumme 648
|
|
| Nach oben |
|
|
fwo
Caterpillar D9
Anmeldungsdatum: 05.02.2008
Beiträge: 26512
Wohnort: im Speckgürtel
|
| (#1646717) Verfasst am: 07.06.2011, 21:12 Titel: |
|
|
| nocquae hat folgendes geschrieben: | .....
Java, wenn es langsam sein und nur sporadisch funktionieren soll. |
 Jetzt weiß ich endlich, warum SAP immer stärker auf JAVA setzt.
fwo
_________________
Ich glaube an die Existenz der Welt in der ich lebe.
The skills you use to produce the right answer are exactly the same skills you use to evaluate the answer. Isso.
Es gibt keinen Gott. Also: Jesus war nur ein Bankert und alle Propheten hatten einfach einen an der Waffel (wenn es sie überhaupt gab).
|
|
| Nach oben |
|
|
Namronia
1500+ mal Qualität!
Anmeldungsdatum: 23.01.2008
Beiträge: 1687
|
| (#1646719) Verfasst am: 07.06.2011, 21:17 Titel: |
|
|
| nocquae hat folgendes geschrieben: | | Namronia hat folgendes geschrieben: | | esme hat folgendes geschrieben: | | Warum willst du die Quersumme berechnen? |
Wir haben gerade in der Berufsschule nicht all zu viel zu tun und wir haben Project Euler gefunden. Ne Seite, mit mathematischen Problemen, die man irgendwie durch Software lösen muss. Und eines davon war genau das hier, aber ich habs zum Glück geschafft |
Aber warum denn in Perl?
Da liegen doch nun wirklich nicht dessen Stärken.
Ich hab mal zur Übung ein Programm zur Primfaktorzerlegung einmal in C++ und einmal in Python geschrieben – Wo C++ noch ca. 30 min brauchte, lag Python schon bei ca. 4 Stunden.
Python wenn es einfach sein und funktionieren soll,
C++ wenn es zeitkritisch ist,
Perl wenn es um Reintext geht,
Java, wenn es langsam sein und nur sporadisch funktionieren soll. |
Ein anderer Klasssenkamerad hatte in Perl angefangen, und wir habens dann auch damit zu Ende gebracht.
Und ja, du hasts perfekt zusammengefasst, was wann 
|
|
| Nach oben |
|
|
gollrich
superheftig general
Anmeldungsdatum: 06.12.2007
Beiträge: 1098
Wohnort: Mannheim
|
| (#1646720) Verfasst am: 07.06.2011, 21:17 Titel: |
|
|
| fwo hat folgendes geschrieben: | | nocquae hat folgendes geschrieben: | .....
Java, wenn es langsam sein und nur sporadisch funktionieren soll. |
Jetzt weiß ich endlich, warum SAP immer stärker auf JAVA setzt.
fwo |
nee nee das liegt dann nur an der Inkompetenz des Entwicklers....
|
|
| Nach oben |
|
|
boomklever
Impfgegnergegner
Anmeldungsdatum: 25.07.2006
Beiträge: 11112
Wohnort: Stuttgart
|
| (#1646738) Verfasst am: 07.06.2011, 21:53 Titel: |
|
|
| nocquae hat folgendes geschrieben: |
Perl wenn es um Reintext geht
|
Du und deine Perl-Phobie. ^^ Text parsen ist eine der Stärken Perls, bei weitem nicht sein einziger Einsatzbereich. Es gibt einige Einsatzbereiche, in denen Perl wirklich keine gute Figur macht - z.B. Treiber-Programmierung oder am anderen Ende der Skala graphische Office-Suites. Bei den meisten Anwendungen, die dazwischen liegen ist Perl eine gut geeignete Sprache.
Edit: Dummschwätz entfernt.
_________________
Don't gift pearls before casting an octopus in a movie.
-- Cherry (ACNH)
|
|
| Nach oben |
|
|
Critic
oberflächlich
Anmeldungsdatum: 22.07.2003
Beiträge: 16358
Wohnort: Arena of Air
|
| (#1646799) Verfasst am: 08.06.2011, 02:58 Titel: |
|
|
Hab's eben in Java implementiert, der Umbruch im Code-Feld wurde im übrigen von PHPBB produziert. Habe ich wenigstens mal die Klasse BigInteger kennengelernt.
(Jawohl, synthetische Benchmarks bilden nicht alles ab, was bei der Entscheidung für eine Sprache relevant sein könnte  .)
| Code: |
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
QS(100!) = 648
|
_________________
"Die Pentagon-Gang wird in der Liste der Terrorgruppen geführt"
Dann bin ich halt bekloppt. 
"Wahrheit läßt sich nicht zeigen, nur erfinden." (Max Frisch)
|
|
| Nach oben |
|
|
jagy
Herb Derpington III.
Anmeldungsdatum: 26.11.2006
Beiträge: 7275
|
| (#1646838) Verfasst am: 08.06.2011, 10:24 Titel: Re: Quersumme von 100! |
|
|
| Namronia hat folgendes geschrieben: | Stimmt das Ergebnis? 648?
|
Für sowas ist ja Wolfram Alpha gut:
| Code: | | http://www.wolframalpha.com/input/?i=sum%20of%20digits%20100! |
_________________
INGLIP HAS BEEN SUMMONED - IT HAS BEGUN!
|
|
| Nach oben |
|
|
Namronia
1500+ mal Qualität!
Anmeldungsdatum: 23.01.2008
Beiträge: 1687
|
| (#1646867) Verfasst am: 08.06.2011, 12:07 Titel: Re: Quersumme von 100! |
|
|
| jagy hat folgendes geschrieben: | | Namronia hat folgendes geschrieben: | Stimmt das Ergebnis? 648?
|
Für sowas ist ja Wolfram Alpha gut:
| Code: | | http://www.wolframalpha.com/input/?i=sum%20of%20digits%20100! |
|
Danke, aber dann wäre das ja langweilig und nicht gerade Sinn des "Spiels"
|
|
| Nach oben |
|
|
Sanne
gives peas a chance.
Anmeldungsdatum: 05.08.2003
Beiträge: 12088
Wohnort: Nordschland
|
| (#1646869) Verfasst am: 08.06.2011, 12:20 Titel: |
|
|
Gibts außer mir noch jemanden, der das Ausrufezeichen in der Überschrift mißinterpretiert und spontan im Kopf ausgerechnet hat:
1 + 0 + 0 = 1
_________________
Ich will das Internet doch nicht mit meinen Problemen belästigen! (Marge Simpson)
|
|
| Nach oben |
|
|
Sri YUKTEREZ
registrierter User
Anmeldungsdatum: 12.01.2007
Beiträge: 223
|
| (#1646870) Verfasst am: 08.06.2011, 12:25 Titel: |
|
|
Auf die Gefahr hin dass man mich jetzt auslachen wird...
Quersummen Berechner
EDIT: ich sehe, hier ist die Rede nicht von 100 sondern von 100 Fakultät... Da ist mein Link natürlich wertlos
|
|
| Nach oben |
|
|
fwo
Caterpillar D9
Anmeldungsdatum: 05.02.2008
Beiträge: 26512
Wohnort: im Speckgürtel
|
| (#1646873) Verfasst am: 08.06.2011, 12:38 Titel: |
|
|
| Sanne hat folgendes geschrieben: | Gibts außer mir noch jemanden, der das Ausrufezeichen in der Überschrift mißinterpretiert und spontan im Kopf ausgerechnet hat:
1 + 0 + 0 = 1 |
Ja, mich. Allerdings war das ein Grund, den Post zu lesen und da stand es ausgeschrieben.....
fwo
_________________
Ich glaube an die Existenz der Welt in der ich lebe.
The skills you use to produce the right answer are exactly the same skills you use to evaluate the answer. Isso.
Es gibt keinen Gott. Also: Jesus war nur ein Bankert und alle Propheten hatten einfach einen an der Waffel (wenn es sie überhaupt gab).
|
|
| Nach oben |
|
|
Norm
registrierter User
Anmeldungsdatum: 12.02.2007
Beiträge: 8149
|
| (#1646883) Verfasst am: 08.06.2011, 13:27 Titel: |
|
|
| fwo hat folgendes geschrieben: | | Sanne hat folgendes geschrieben: | Gibts außer mir noch jemanden, der das Ausrufezeichen in der Überschrift mißinterpretiert und spontan im Kopf ausgerechnet hat:
1 + 0 + 0 = 1 |
Ja, mich. Allerdings war das ein Grund, den Post zu lesen und da stand es ausgeschrieben.....
fwo |
Ja, ich auch.
|
|
| Nach oben |
|
|
nocquae
diskriminiert nazis
Anmeldungsdatum: 16.07.2003
Beiträge: 18183
|
| (#1646953) Verfasst am: 08.06.2011, 16:47 Titel: |
|
|
| joran hat folgendes geschrieben: | | nocquae hat folgendes geschrieben: |
Perl wenn es um Reintext geht
|
Du und deine Perl-Phobie. ^^ Text parsen ist eine der Stärken Perls, bei weitem nicht sein einziger Einsatzbereich. Es gibt einige Einsatzbereiche, in denen Perl wirklich keine gute Figur macht - z.B. Treiber-Programmierung oder am anderen Ende der Skala graphische Office-Suites. Bei den meisten Anwendungen, die dazwischen liegen ist Perl eine gut geeignete Sprache. |
| Zitat: | | Edit: Dummschwätz entfernt. |
Stimmt ja gar nicht.
_________________
In Deutschland gilt derjenige, der auf den Schmutz hinweist, als viel gefährlicher, als derjenige, der den Schmutz macht.
-- Kurt Tucholsky
|
|
| Nach oben |
|
|
nocquae
diskriminiert nazis
Anmeldungsdatum: 16.07.2003
Beiträge: 18183
|
| (#1646955) Verfasst am: 08.06.2011, 16:48 Titel: |
|
|
| Critic hat folgendes geschrieben: | Hab's eben in Java implementiert, der Umbruch im Code-Feld wurde im übrigen von PHPBB produziert. Habe ich wenigstens mal die Klasse BigInteger kennengelernt.
(Jawohl, synthetische Benchmarks bilden nicht alles ab, was bei der Entscheidung für eine Sprache relevant sein könnte .)
| Code: |
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
QS(100!) = 648
|
|
Stimmt das tatsächlich? Die 24 Nullen am Ende kommen mir eher so vor, als wären zwischendurch irgendwelche Datentypen an ihre Grenzen gestoßen und die Summe am Ende mit Nullen aufgefüllt, um auf die richtige Stellenzahl zu kommen.
_________________
In Deutschland gilt derjenige, der auf den Schmutz hinweist, als viel gefährlicher, als derjenige, der den Schmutz macht.
-- Kurt Tucholsky
|
|
| Nach oben |
|
|
fwo
Caterpillar D9
Anmeldungsdatum: 05.02.2008
Beiträge: 26512
Wohnort: im Speckgürtel
|
| (#1646966) Verfasst am: 08.06.2011, 17:16 Titel: |
|
|
| nocquae hat folgendes geschrieben: | | Critic hat folgendes geschrieben: | Hab's eben in Java implementiert, ....
| Code: |
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
QS(100!) = 648
|
|
Stimmt das tatsächlich? Die 24 Nullen am Ende kommen mir eher so vor, als wären zwischendurch irgendwelche Datentypen an ihre Grenzen gestoßen und die Summe am Ende mit Nullen aufgefüllt, um auf die richtige Stellenzahl zu kommen. |
Glaube ich nicht. Allein die Faktoren 10, 20 ...100 sorgen für 11 Nullen am Ende. Nun nimm noch die Zahlen außer den gerade aufgezählten dazu, die den Faktor 5 enthalten: das dürfte gegenüber dem häufigeren Faktor 2 der limitierende Faktor sein und nach Pi mal Daumen würde ich sagen: Passt schon und wenn es nicht so wäre, wäre eher ein Fehler drin.
Es wäre auch komisch, dass Critic und Wolfram den selben Fehler gemacht hätten - die kommen nämlich auf die selbe Quersumme 
fwo
_________________
Ich glaube an die Existenz der Welt in der ich lebe.
The skills you use to produce the right answer are exactly the same skills you use to evaluate the answer. Isso.
Es gibt keinen Gott. Also: Jesus war nur ein Bankert und alle Propheten hatten einfach einen an der Waffel (wenn es sie überhaupt gab).
|
|
| Nach oben |
|
|
nocquae
diskriminiert nazis
Anmeldungsdatum: 16.07.2003
Beiträge: 18183
|
| (#1646975) Verfasst am: 08.06.2011, 17:31 Titel: |
|
|
| fwo hat folgendes geschrieben: | | Es wäre auch komisch, dass Critic und Wolfram den selben Fehler gemacht hätten - die kommen nämlich auf die selbe Quersumme |
Das wäre ein Argument, wenn das von Hand berechnet würde. Was ich für eher unwahrscheinlich halte. Es sei denn, bei Wolfram alpha säße Rainman am anderen Ende der Leitung.
In der Praxis spielen eher limitierende Faktoren der IT eine Rolle, und die sind u. U. ähnlicher, als man glaubt.
„Das ist mathematisch korrekt“ würde ich dagegen als Antwort akzeptieren.
_________________
In Deutschland gilt derjenige, der auf den Schmutz hinweist, als viel gefährlicher, als derjenige, der den Schmutz macht.
-- Kurt Tucholsky
|
|
| Nach oben |
|
|
esme
lebt ohne schützende Gänsefüßchen.
Anmeldungsdatum: 12.06.2005
Beiträge: 5667
|
| (#1646976) Verfasst am: 08.06.2011, 17:35 Titel: |
|
|
100/5+100/25=20+4=24 Nullen.
_________________
Gunkl über Intelligent Design:
Da hat sich die Kirche beim Rückzugsgefecht noch einmal grandios verstolpert und jetzt wollen sie auch noch Haltungsnoten für die argumentative Brez'n, die sie da gerissen haben.
|
|
| Nach oben |
|
|
pera
auf eigenen Wunsch deaktiviert
Anmeldungsdatum: 01.07.2009
Beiträge: 4256
|
| (#1646979) Verfasst am: 08.06.2011, 17:43 Titel: |
|
|
| esme hat folgendes geschrieben: | | 100/5+100/25=20+4=24 Nullen. |
Wollt ich grade schreiben.
Bin aber zu blöd die Summenformel richtig darzustellen.
|
|
| Nach oben |
|
|
fwo
Caterpillar D9
Anmeldungsdatum: 05.02.2008
Beiträge: 26512
Wohnort: im Speckgürtel
|
| (#1646983) Verfasst am: 08.06.2011, 17:57 Titel: |
|
|
| nocquae hat folgendes geschrieben: | | fwo hat folgendes geschrieben: | | Es wäre auch komisch, dass Critic und Wolfram den selben Fehler gemacht hätten - die kommen nämlich auf die selbe Quersumme |
Das wäre ein Argument, wenn das von Hand berechnet würde. Was ich für eher unwahrscheinlich halte. Es sei denn, bei Wolfram alpha säße Rainman am anderen Ende der Leitung.
In der Praxis spielen eher limitierende Faktoren der IT eine Rolle, und die sind u. U. ähnlicher, als man glaubt.
„Das ist mathematisch korrekt“ würde ich dagegen als Antwort akzeptieren. |
Dann machen wir es ohne Rainman im Kopf: Die Zahlen 1 bis 100 enthalten 20 Zahlen, die durch 5 teilbar sind, 4 davon sind sogar duch 25 teilbar, sodass das Produkt 100! den Primfaktor 5 genau 24 mal enthält. Die Betrachtung der 2 kann ich mir sparen : Es ist mathematisch korrekt, dass 100! 24 Nullen am Ende hat.
Zu den Datentypen müsste mal jetzt jemand kommen, der sich mit dem BigInt in Java auskennt. Ich bin davon ausgegangen, dass es sich hier tatsächlich um einen Ziffernarray handelt, auf dem die Maschine so rechnet, wie wir es schriftlich tun - so hätte ich es selbst gemacht. Da kommst Du dann in den Zwischenschritten auch theoretisch nicht in die Nähe irgendwelcher Überlaufgefahren.
uups, da waren welche schneller.
fwo
_________________
Ich glaube an die Existenz der Welt in der ich lebe.
The skills you use to produce the right answer are exactly the same skills you use to evaluate the answer. Isso.
Es gibt keinen Gott. Also: Jesus war nur ein Bankert und alle Propheten hatten einfach einen an der Waffel (wenn es sie überhaupt gab).
|
|
| Nach oben |
|
|
Mahone
registrierter User
Anmeldungsdatum: 22.12.2008
Beiträge: 842
Wohnort: Munich
|
| (#1646996) Verfasst am: 08.06.2011, 19:02 Titel: |
|
|
| nocquae hat folgendes geschrieben: | | joran hat folgendes geschrieben: | | nocquae hat folgendes geschrieben: |
Perl wenn es um Reintext geht
|
Du und deine Perl-Phobie. ^^ Text parsen ist eine der Stärken Perls, bei weitem nicht sein einziger Einsatzbereich. Es gibt einige Einsatzbereiche, in denen Perl wirklich keine gute Figur macht - z.B. Treiber-Programmierung oder am anderen Ende der Skala graphische Office-Suites. Bei den meisten Anwendungen, die dazwischen liegen ist Perl eine gut geeignete Sprache. |
| Zitat: | | Edit: Dummschwätz entfernt. |
Stimmt ja gar nicht. |
|
|
| Nach oben |
|
|
Critic
oberflächlich
Anmeldungsdatum: 22.07.2003
Beiträge: 16358
Wohnort: Arena of Air
|
| (#1647068) Verfasst am: 09.06.2011, 00:56 Titel: |
|
|
| nocquae hat folgendes geschrieben: | | Critic hat folgendes geschrieben: | Hab's eben in Java implementiert, der Umbruch im Code-Feld wurde im übrigen von PHPBB produziert. Habe ich wenigstens mal die Klasse BigInteger kennengelernt.
(Jawohl, synthetische Benchmarks bilden nicht alles ab, was bei der Entscheidung für eine Sprache relevant sein könnte .)
| Code: |
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
QS(100!) = 648
|
|
Stimmt das tatsächlich? Die 24 Nullen am Ende kommen mir eher so vor, als wären zwischendurch irgendwelche Datentypen an ihre Grenzen gestoßen und die Summe am Ende mit Nullen aufgefüllt, um auf die richtige Stellenzahl zu kommen. |
Tatsache ist: das habe ich zuerst auch gedacht. Ich hatte mir dann auch alle Zwischenwerte anzeigen lassen, um das nachzuvollziehen.
(2) | fwo hat folgendes geschrieben: | | Zu den Datentypen müsste mal jetzt jemand kommen, der sich mit dem BigInt in Java auskennt. Ich bin davon ausgegangen, dass es sich hier tatsächlich um einen Ziffernarray handelt, auf dem die Maschine so rechnet, wie wir es schriftlich tun - so hätte ich es selbst gemacht. Da kommst Du dann in den Zwischenschritten auch theoretisch nicht in die Nähe irgendwelcher Überlaufgefahren. |
Naja, "auskennen": Es gibt jedenfalls eine Implementierung mit Sun-Copyright auf einer Open-Source-Seite - über Lizenzfragen wollte ich mich nicht auslassen - (Link), das könnte also die gelieferte (oder zumindest eine Vorversion davon) sein.
Ein Wert wird dort in einem Array von Werten vom Typ int gespeichert, der dargestellte Wert kann also zunächst einmal beinahe beliebig groß werden. Bei der Multiplikation wird im Prinzip die Schulmethode implementiert, natürlich blockweise in der entsprechenden Länge, und Überträge werden auf das Element des Arrays addiert, das den nächsthöheren Block des Ergebnisses darstellt.
_________________
"Die Pentagon-Gang wird in der Liste der Terrorgruppen geführt"
Dann bin ich halt bekloppt.
"Wahrheit läßt sich nicht zeigen, nur erfinden." (Max Frisch)
|
|
| Nach oben |
|
|
brf
registrierter User
Anmeldungsdatum: 25.05.2010
Beiträge: 366
|
| (#1647460) Verfasst am: 09.06.2011, 23:15 Titel: |
|
|
| fwo hat folgendes geschrieben: | ...
Zu den Datentypen müsste mal jetzt jemand kommen, der sich mit dem BigInt in Java auskennt. Ich bin davon ausgegangen, dass es sich hier tatsächlich um einen Ziffernarray handelt, auf dem die Maschine so rechnet, wie wir es schriftlich tun - so hätte ich es selbst gemacht. |
Stimmt. Halb. Sie rechnen mit Bytes in einem Zahlensystem zur Basis 256 (nicht 10) und sie verwenden ausgefeilte Multiplikationsalgorithmen, die weit von den Handalgorithmen entfernt sind. Aber dafür schnell.
Ein ähnlich schnelles Paket für C/C++ ist übrigens GMP (Gnu Multiple Precision)
Auf niedrigerem Niveau aber verständlicher ist es in den numerical Recipes erläutert, wo zur Multiplikation eine FastFourierTranfo (FFT) verwendet wird.
http://www.nrbook.com/a/bookcpdf/c20-6.pdf
|
|
| Nach oben |
|
|
Critic
oberflächlich
Anmeldungsdatum: 22.07.2003
Beiträge: 16358
Wohnort: Arena of Air
|
| (#1647477) Verfasst am: 09.06.2011, 23:54 Titel: |
|
|
| brf hat folgendes geschrieben: | | fwo hat folgendes geschrieben: | ...
Zu den Datentypen müsste mal jetzt jemand kommen, der sich mit dem BigInt in Java auskennt. Ich bin davon ausgegangen, dass es sich hier tatsächlich um einen Ziffernarray handelt, auf dem die Maschine so rechnet, wie wir es schriftlich tun - so hätte ich es selbst gemacht. |
Stimmt. Halb. Sie rechnen mit Bytes in einem Zahlensystem zur Basis 256 (nicht 10) und sie verwenden ausgefeilte Multiplikationsalgorithmen, die weit von den Handalgorithmen entfernt sind. Aber dafür schnell.
Ein ähnlich schnelles Paket für C/C++ ist übrigens GMP (Gnu Multiple Precision)
Auf niedrigerem Niveau aber verständlicher ist es in den numerical Recipes erläutert, wo zur Multiplikation eine FastFourierTranfo (FFT) verwendet wird.
http://www.nrbook.com/a/bookcpdf/c20-6.pdf |
(Vielleicht sollte ich mir angewöhnen, Gedanken auch auszuschreiben:) Wie gesagt, kann man auf verschiedene Arten multiplizieren. Es geht deutlich effizienter -- wenn auch mit zum Teil sehr viel mehr Denkaufwand beschrieben, aber das ist ja so einer der Trade-Offs hierbei -- als per Schulmethode (Beispiel: Karatsuba-Algorithmus, oder bei Schönhage-Strassen mit Hilfe der "superschnellen Fourier-Transformation"). Die verlinkte Implementierung von BigInteger leidet abgesehen von der Effizienz auch unter anderen Performance-Schwächen (es werden dort ja immer Objekte erzeugt, und ein Objekt zu instanziieren nimmt um Größenordnungen mehr Zeit in Anspruch als die reine Multiplikation).
_________________
"Die Pentagon-Gang wird in der Liste der Terrorgruppen geführt"
Dann bin ich halt bekloppt.
"Wahrheit läßt sich nicht zeigen, nur erfinden." (Max Frisch)
|
|
| Nach oben |
|
|
brf
registrierter User
Anmeldungsdatum: 25.05.2010
Beiträge: 366
|
| (#1647513) Verfasst am: 10.06.2011, 07:45 Titel: |
|
|
| Critic hat folgendes geschrieben: | ...
(Beispiel: Karatsuba-Algorithmus, oder bei Schönhage-Strassen mit Hilfe der "superschnellen Fourier-Transformation"). Die verlinkte Implementierung von BigInteger leidet abgesehen von der Effizienz auch unter anderen Performance-Schwächen (es werden dort ja immer Objekte erzeugt, und ein Objekt zu instanziieren nimmt um Größenordnungen mehr Zeit in Anspruch als die reine Multiplikation). |
Zwei Fragen:
1. Ich kenne die schnelle Fouriertrafo, aber keine superschnelle. Gibts da eine Neuentwicklung, die schneller als O(n*log(n)) ist=
2. Die Algorithmen bei BigInteger sind (meines Wissens) die besten heute verfügbaren. Die (immer wieder in der Ring geworfenenen) "Performanceschwächen" sind eigentlich nur den Preis, den man für Objektorientierung zahlen muss. OO ist für viele Probleme nicht wegzudenken, weil Programme ohne OO mehr (zu viel) Entwicklungzeit brauchen und schlechter (viel zu schlecht) wartbar wären.
Rekursion hat in den 1960er Jahren einen ähnlichen Preis gefordert und viele (alte Assembler-)Programmierer haben damals argumentiert, Rekursion wäre zu langsam. Umgekehrt wird ein Schuh draus: Ohne Rekursion stünden wir noch auf dem Programmstand von etwa 1970. Ohne OO gäbe es nur Programme wie 1980.
Nun zur Frage: Woher hast Du Informationen, dass Objekterzeugung mehr Zeit in Anspruch nimmt als Multiplikation? Objekterzeugung dauert wenige zig Nanosekunden. Multiplikation mit FFT (z.B.) ist O (nlog(n)). Bei n=10000 sind das schon Millisekunden, bei n=1000000 geht das in den Sekundenbereich.
|
|
| Nach oben |
|
|
|
FAQ 
Suchen 
Mitgliederliste 
Nutzungsbedingungen 
Benutzergruppen 
Links
Registrieren
Profil 
Einloggen, um private Nachrichten zu lesen 
Login 
