Svenska ElektronikForumet

Ett litet tips om man inte tänkt på det är
att det går att kvadrera vissa tal genom att utföra endast
addition.

1 + 3 + 5 + ...(2n -1) = n^2

Kan kanske vara användbart i vissa sammanhang.

Ex.

7^2 = 1 + 3 + 5 + 7 + 9 + 11 + 13

Men hur räknar du fram (2n-1) snabbare än att multiplicera ett tal med sig själv?

Iofs, en vänsterskift och sen en subtraktion...

Men går inte 7+7+7+7+7+7+7 lika snabbt som 1+3+5+7+9+11+13? Det är ju 7 additioner i vilket fall som helst...

Just att räkna fram serien 1, 3, 5, 7, 9 osv måste ju kräva en addition för varje steg?

För de processorer som inte har HW multiplikation så kan nog den här metoden vara snabbare för små tal.

Men vad gör den snabbare än 7+7+7+7+7+7+7?
måste väl ändå vara det snabbaste sättet att kvadrera?

annars blir det ju
eller finns det nåt snabbare sätt att implementera det?

Snabbhet är inte det viktigaste i alla sammanhang.
Kan finnas situationer då regeln är användbar som
leder till enkelhet.

Säg att jag vill beräkna 6^2

1+3+5+7+9 = 25

36 = 25 +11 = 6^2

Alltså additionen 25 + 11 ska utföras i stället för multiplikationen 6*6

I det fallet kan du väl ersätta 6^2 med 36 direkt...

Det är väl x^2 som är det man vill ha en algoritm för...

Sen kan jag inte se hur:
1+3+5+7+9 = 25
36 = 25 +11 = 6^2

skiljer sig från:
6+6+6+6+6 = 30
36 = 30 + 6 = 6^2
mer än att det är krångligare att komma fram till första exemplets lista med värden.

Jag tror att 4kTRB försöker säga att om man t.ex. ska räkna ut kvadraten för tal som är 5 eller högre så kan man utgå från 25 och sen addera 11, 13, 15, 17 etc beroende på hur mycket högre än 5 värdet är.

MEN, problemet som återkommer där är ju: Hur vet du att du för 6 ska addera 11 och för 7 ska addera 11 och 13? Det måste räknas eller fås ur tabell och då är vi väl tillbaka i ruta 1 igen?

Skriv det med pseudoalgoritm som jag gjorde så ser du fallgroparna.

Idéen är bra men istället för att stega upp värden är det nog enklare att hålla samma värde och göra rätt antal iterationer.

TS' idé:
Börja med Resultat = 0 och Mellanvärde = 1.
Steg A: Resultat = Resultat + Mellanvärde.
Steg B: Mellanvärde = Mellanvärde + 2.
Steg C: Upprepa n gg.

"Bättre" idé:
Börja med Resultat = 0 och Mellanvärde = n.
Steg A: Resultat = Resultat + Mellanvärde.
Steg B: Upprepa N gångar.

Man sparar alltså ett steg vid att bara hårdköra med samma värde. Sedan är det inte så tidsekonomisk vid högre värden där en mjukvaramultiplikation blir snabbare. Beroende på hur effektiv man koder kan det röra sig om ett värde runt 10^2 där additionen kontra mjukvaramultiplikation går jämt ut.

Så kul grej, det finns kanske tillfällen där det är rätt sak men ur effektivitetssynpunkt är den näst bäst.

Till exempel vilket blir snabbast av de här 2 alternativen:

1 + 2*2 + 3*3 + 4*4

1 + 1 + 3 + 1 + 3 + 5 + 1 + 3 + 5 + 7

?

3st + och 3st *
eller 9st +

Om det inte finns HW multiplikation så antagligen additionerna underst.
Men det går i så fall lika snabbt med följande i så fall:
1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 (också det 9 additioner) och då behöver man inte ta reda på att det är 1, 3, 5, 7 man behöver för att räkna ut 4*4.

Se Icecaps inlägg om algoritmer

Om vi frånser tillfällen där det finns HW-multiplikator och vi håller oss till en byte i storlek kräver en mjukvara-multiplikation 8 steg:
0: Resultat = 0;
1: Om LSB på Värde1 är '0' hopp till steg 3.
2: Resultat = Resultat + Värde2.
3: Värde1 / 2 (shift right ett steg)
4: Värde2 * 2 (shift left ett steg)
5: Upprepa 8 gg

Detta kommer att ta runt 10-12 instruktioner per cykel, alltså totalt runt 80-100 instruktioner för en 8-bit multiplikation.

Additionen tar färre instruktioner men ska itereras längre vid högre värden. Om man antar att additionerna tar ungefär 4 instruktioner för varje cykel blir det en gräns runt 20-24 där det är break-even i tidförbrukning, under det värde är det snabbaste additionsmetoden och över är det multiplikationen som vinner.

4kTRB skrev:Till exempel vilket blir snabbast av de här 2 alternativen:

1 + 2*2 + 3*3 + 4*4

1 + 1 + 3 + 1 + 3 + 5 + 1 + 3 + 5 + 7

?

3st + och 3st *
eller 9st +

Vad går snabbast?
1 + 3 + 5 + 7 + 9 + 11
6 + 6 + 6 + 6 + 6 + 6

De två alternativen tar nog ungefär lika många klockcykler.

Glöm inte att det här är ett tips som går att utnyttja i
vissa situationer och det är lätt hänt att man inte tänkte
på just det här alternativet för kvadrering.

Jag har ju skrivit pseudokod för bägge varianterna och 6+6+6... blir ju kortare eftersom man slipper räkna upp termen man adderar. Ska man addera 1+3+5 osv så måste man ju addera två varje gång?

Precis som jag skrev i mitt tidigare inlägg...