mikrocontroller.net

Forum: Offtopic Berechnung von (2002)^6


Autor: Trick gesucht (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da wird nicht zufaellig in nem Restklassenring mod n gerechnet?
So oder so: Versuch es mal hiermit:
http://de.wikipedia.org/wiki/Schnelles_Potenzieren

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Zahlen sind so beschaffen, dass man das vollständige Ergebnis auch
leicht und ohne viel zu denken mit Papier und Bleistift ausrechnen kann:
2002⁶ = 2⁶·(1000+1)⁶
= 64·(1000⁶+6·1000⁵+15·1000⁴+20·1000³+15·1000²+6·1000+1)
= 64·10¹⁸+384·10¹⁵+960·10¹²+1280·10⁹+960·10⁶+384·10³+64
=   64000000000000000000
  +   384000000000000000
  +      960000000000000
  +        1280000000000
  +            960000000
  +               384000
  +                   64
=   64384961280960384064

Autor: Steed (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oje, Oje das ist Mathematik 6. oder 7. Klasse.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Steed (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Karl-heinz Strunk (cletus)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>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)

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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?"

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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-Strass...
   http://de.wikipedia.org/wiki/Karatsuba-Algorithmus

Naja, es heisst wohl "schnell" weil es noch was langsameres gibt.

...aber das gibt's immer...

Autor: Steed (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Jürgen A. (jaja)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.