Hallo, ich soll die ersten 4 Stellen von 2002^6 bestimmen. Sinn der Sache ist es ja wohl nicht das Ganze in den Taschenrechner einzugeben. (Habe ich schon gemacht, Ergebnis ist 6438). Da sollte es ja wohl irgendeinen Trick geben. Nur wo?
Schon die binomischen Formeln versucht?
Die ersten Stellen sollten also mit denen von 32*2012 übereinstimmen, weil Vielfache von 1000 nix an den Ziffern drehen. Zu begründen ist noch, daß man das Zeug in den ... vernachlässigen kann. Johann
Mein erster Gedanke wäre mal die Binomische Formel zu benutzen
(a+b)^6 = 1 a^6 b^0
+ 6 a^5 b^1
+15 a^4 b^2
+20 a^3 b^3 mit a = 2000
+15 a^2 b^5 b = 2
+ 6 a^1 b^5
+ 1 a^0 b^6
Kein Ahnung, ob das was hilft..
Vielleicht lässt sich so abschätzen, wievel Terme man benötigt
http://de.wikipedia.org/wiki/Pascalsches_Dreieck
Es geht noch besser wenn man nimmt
und weil binom (6, n) < 1000 ist. Damit gibt es von einem 3er-Ziffernpaket kein Übertrag beim Potenzieren (genauso wie 1001^2 = 1002001). Daher ist
weil
Weiterhin muss man noch überlegen, daß sich die 3er-Pakete nicht (zu stark) durch die Multiplikation mit 64 beeinflussen. Etwa ist 64*15 < 1000, d.h. die ersten 4 Stellen werden dadurch nicht beeinflusst. Johann
Da wird nicht zufaellig in nem Restklassenring mod n gerechnet? So oder so: Versuch es mal hiermit: http://de.wikipedia.org/wiki/Schnelles_Potenzieren
Michael G. wrote: > Da wird nicht zufaellig in nem Restklassenring mod n gerechnet? Daraus erhält man keine Aussagen über die führenden Ziffern, bestenfalls über die niederwertigsten. > So oder so: Versuch es mal hiermit: > http://de.wikipedia.org/wiki/Schnelles_Potenzieren Ich hab mich immer gefragt, was daran "schnell" sein soll. Eine Multiplikation heisst ja auch nicht "schnell", nur weil man 12*17 mit der Schulmethode ausrechnet, anstatt 12 mal 17 aufzuaddieren... :o) Johann
Die Zahlen sind so beschaffen, dass man das vollständige Ergebnis auch leicht und ohne viel zu denken mit Papier und Bleistift ausrechnen kann:
1 | 2002⁶ = 2⁶·(1000+1)⁶ |
2 | = 64·(1000⁶+6·1000⁵+15·1000⁴+20·1000³+15·1000²+6·1000+1) |
3 | = 64·10¹⁸+384·10¹⁵+960·10¹²+1280·10⁹+960·10⁶+384·10³+64 |
4 | = 64000000000000000000 |
5 | + 384000000000000000 |
6 | + 960000000000000 |
7 | + 1280000000000 |
8 | + 960000000 |
9 | + 384000 |
10 | + 64 |
11 | = 64384961280960384064 |
Steed wrote:
> Oje, Oje das ist Mathematik 6. oder 7. Klasse.
Und wo so oft, besteht das Problem darin, die entscheidende Idee zu
haben. Hast du die nicht, ist es völlig egal auf welchem
Schwiergkeitsgrad sich die dahintersteckende Mathe bewegt.
Der Threadopener hatte diese Idee nicht. Vielleicht hat er noch nie eine
Anwendung der BF in dieser Form gesehen? Willst du ihm jetzt daraus
einen Strick drehen?
>Willst du ihm jetzt daraus einen Strick drehen?
Ja, denn wenn er nur mit halben Ohr hingehört hätte, was man ihm
versucht hat beizubringen, so wüsste er was zu tun ist. Wenn die Potenz
nicht wäre könnte man sogar von Mathematik der 2. Klasse sprechen.
Steed wrote:
> Wenn die Potenz nicht wäre könnte man sogar von Mathematik der 2. Klasse
sprechen.
Wie gut, dass du kein Lehrer bist.
>>Willst du ihm jetzt daraus einen Strick drehen? >Ja, denn wenn er nur mit halben Ohr hingehört hätte, was man ihm >versucht hat beizubringen, so wüsste er was zu tun ist. Wenn die Potenz >nicht wäre könnte man sogar von Mathematik der 2. Klasse sprechen. Dann poste doch mal Deine ultimative, 7te-Klasse Lösung... Wir sind alle schon sehr gespannt (einer aus der 5.Klasse)
Johann L. wrote: >> So oder so: Versuch es mal hiermit: >> http://de.wikipedia.org/wiki/Schnelles_Potenzieren > > Ich hab mich immer gefragt, was daran "schnell" sein soll. "Bei der einfachen und langsamen Potenzierung von ac multipliziert man a (c − 1)-mal mit sich selbst. Beim „Square & Multiply“ werden lediglich log2(c) Schleifendurchläufe benötigt (log2(c) entspricht hierbei ungefähr der Länge der Zahl c in der Binärdarstellung)." Davon abgesehen dass man gerade im Restklassenring mit deutlich kleineren Zahlen rechnet.
Steed wrote: > Wenn die Potenz nicht wäre könnte man sogar von Mathematik der 2. Klasse > sprechen. Woe sähe die Aufgabe denn ohne Potenz aus? Doe ersten 4 Stellen von 2002 bestimmen? Man, was für Scheiße manche hier doch immer absondern müssen...
>Doe ersten 4 Stellen von 2002 bestimmen? Man, was für Scheiße manche >hier doch immer absondern müssen... Das könnte dann so eine Quiz-Kabel-EIns Frage sein. NAch dem Motto "Welche Farbe hat das gelbe Schild?"
Michael G. wrote: > Johann L. wrote: > >>> So oder so: Versuch es mal hiermit: >>> http://de.wikipedia.org/wiki/Schnelles_Potenzieren >> >> Ich hab mich immer gefragt, was daran "schnell" sein soll. > > "Bei der einfachen und langsamen Potenzierung von ac multipliziert man a > (c − 1)-mal mit sich selbst. Beim „Square & Multiply“ werden lediglich > log2(c) Schleifendurchläufe benötigt (log2(c) entspricht hierbei > ungefähr der Länge der Zahl c in der Binärdarstellung)." Deshalb schrieb ich ja auch: "Eine Multiplikation heisst ja auch nicht "schnell", nur weil man 12*17 mit der Schulmethode ausrechnet, anstatt 12 mal 17 aufzuaddieren... :o)" Die Schul-Multiplikation ist das 1-zu-1 Analogon zur "schnellen" Exponentiation. Ich seh immer noch nicht, was daran schnell sein soll. Es ist die naheliehende Methode zum Potenzieren. Auf die Ideem einfach Aufmultiplizieren, kommt man doch ebensowenig, wie bei einer Multiplikation einfach Aufzuaddieren. Ausser zur Veranschaulichung oder für theoretische Betrachtungen, also wo die Berechnung nicht explizit ausgeführt wird. Bei einer Multiplikation würd ich zB "schnell" sagen, wenn ausgefeilte Verfahren am Werk sind, wie zB Methode von Karatsuba oder Schönhage-Strassen: http://de.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen-Algorithmus http://de.wikipedia.org/wiki/Karatsuba-Algorithmus Naja, es heisst wohl "schnell" weil es noch was langsameres gibt. ...aber das gibt's immer...
>Woe sähe die Aufgabe denn ohne Potenz aus?
vielleicht so?:
2002*2002*2002*2002*2002*2002
Wenn man die Aufgabe nun von Hand ausrechnet, dann weiss man auch wo der
Trick liegt. Das ist ein typisches Problem aus der Informatik und findet
z.B. bei RSA Verwendung. Es geht lediglich darum mit einem Minimum an
Speicher- und Rechenkapzität auszukommen.
Steed wrote: > Oje, Oje das ist Mathematik 6. oder 7. Klasse. und > Das ist ein typisches Problem aus der Informatik und findet > z.B. bei RSA Verwendung. aha! Wird das nicht schon in der 5. Klasse gelehrt?
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.