Litet programmeringstips för beräkning av kvadrater

[4kTRB]

* Kvadrera talet 4
i = 1
k = 0
loop 4ggr {
k = k + i;
i = i + 2;
}

* Resultat: k = 16

Enbart addition inblandat.

[Nerre]

* Kvadrera talet 4

k = 0
loop 4 ggr {
k = k + 4;
}

* Resultat: k = 16

[Zeela]

Jag måste hålla med Nerre, jag ser inte vitsen med din version 4kTRB.
Det blir ju en extra addition för varje varv i loopen.

[Nerre]

Om man på något smart sätt kan använda loopräknaren så blir kanske den lösningen fiffig, men så länge man måste räkna fram den där termen med en extra addition så går det ju bara långsammare.

Skriver man det i "psudoassembler" blir väl den enkla lösningen nåt i stil med:

* kvadrera tal

k=0
i = tal
:loop
k=k+tal
decrement i
if not zero jump loop

[4kTRB]

Jag ville bara visa på att det är
viktigt att använda sambandet på rätt
sätt annars så blir det lätt fel
och ingen mening med.

[monstrum]

Skulle då vara intressant att se ett sådant fall där det är vettigt att göra så här.

[bearing]

Jag kan se ett användningsområde. Man borde kunna implementera denna algoritm utan räknarvariabel, och på så sätt spara minne. Algoritmen borde inte ta längre tid än summeringsloopen.

Psuedokod:

Kod: Markera allt

k = 0
n = (n * 2) - 1
loop:
  k = k + n
  n = n - 2
if Carry goto loop

[monstrum]

Fast du har ju redan använt två variabler.

[bearing]

I Nerres exempel används ju tre, så jag förstår inte vad du vill säga.

[monstrum]

Jag tyckte du föreslog att Nerres metod skulle kunna ha ett användningsområde ifall man implementerade den "baklänges" så som du gjorde i din pseudokod för att "på så sätt spara minne". Ditt exempel använder två variabler.
Jämfört med det enklaste sättet att helt enkelt loopa ett visst antal gånger (en variabel) och addera (en variabel) så har man inte sparat någonting.

[bearing]

Nu blev jag mer förvirrad. Mitt exempel byggde på algoritmen presenterad av trådstartaren (4kTRB). Mitt använder två variabler; basen (n) (som "förbrukas") och kvadraten (k).

Nerres använder tre variabler; basen (tal), kvadraten (k) och en räknare (i) (som "förbrukas").

[monstrum]

Ok, ursäkta jag skrev fel namn. För att förtydliga vad jag ville ha sagt:

Kod: Markera allt

k = 0
n = (n * 2) - 1
loop:
  k = k + n
  n = n - 2
if Carry goto loop

Kod: Markera allt

k = 0
loop 4 ggr {
k = k + 4;
}

Bägge använder två variabler och därmed förstod jag inte varför det skulle finnas ett användningsområde för TS metod, vilket jag antog att du (bearing) menade med "Jag kan se ett användningsområde. Man borde kunna implementera denna algoritm utan räknarvariabel, och på så sätt spara minne".

[bearing]

Men där använder du ju en konstant (4:an). I en generell form (vilket min och nerres kod är) ska ju 4:an inte vara en konstant, utan en variabel, vilket gör att 3 variabler krävs. Den 4 som adderas till k kan ju inte samtidigt användas som räknare.

[monstrum]

Ok, då är jag med hur du menar. Det finns alltså ett användningsområde för denna metod. Ifall man har nåt extra ord programminne över, kan avvara ett par klockcykler och saknar en byte ram, då är TS metod att föredra.

[snigelen]

Om man råkar ha lite FLASH till övers kan man ju göra så här (AVR-gcc-exempel, otestat)

Kod: Markera allt

#include <avr/io.h>
#include <avr/pgmspace.h>

const uint16_t PROGMEM squares[256] = {
        0,1,4,9,16,25,36,49,
        64,81,100,121,144,169,196,225,
        256,289,324,361,400,441,484,529,
        576,625,676,729,784,841,900,961,
        1024,1089,1156,1225,1296,1369,1444,1521,
        1600,1681,1764,1849,1936,2025,2116,2209,
        2304,2401,2500,2601,2704,2809,2916,3025,
        3136,3249,3364,3481,3600,3721,3844,3969,
        4096,4225,4356,4489,4624,4761,4900,5041,
        5184,5329,5476,5625,5776,5929,6084,6241,
        6400,6561,6724,6889,7056,7225,7396,7569,
        7744,7921,8100,8281,8464,8649,8836,9025,
        9216,9409,9604,9801,10000,10201,10404,10609,
        10816,11025,11236,11449,11664,11881,12100,12321,
        12544,12769,12996,13225,13456,13689,13924,14161,
        14400,14641,14884,15129,15376,15625,15876,16129,
        16384,16641,16900,17161,17424,17689,17956,18225,
        18496,18769,19044,19321,19600,19881,20164,20449,
        20736,21025,21316,21609,21904,22201,22500,22801,
        23104,23409,23716,24025,24336,24649,24964,25281,
        25600,25921,26244,26569,26896,27225,27556,27889,
        28224,28561,28900,29241,29584,29929,30276,30625,
        30976,31329,31684,32041,32400,32761,33124,33489,
        33856,34225,34596,34969,35344,35721,36100,36481,
        36864,37249,37636,38025,38416,38809,39204,39601,
        40000,40401,40804,41209,41616,42025,42436,42849,
        43264,43681,44100,44521,44944,45369,45796,46225,
        46656,47089,47524,47961,48400,48841,49284,49729,
        50176,50625,51076,51529,51984,52441,52900,53361,
        53824,54289,54756,55225,55696,56169,56644,57121,
        57600,58081,58564,59049,59536,60025,60516,61009,
        61504,62001,62500,63001,63504,64009,64516,65025
};

uint16_t square(uint8_t i)
{
        return pgm_read_word(&squares[i]);
}

Det blir ju nästan likvärdigt i hastighet med hårdvarumultiplikation. För kvadrater av tal större än 255 kan man kanske kosta på sig en multiplikations-rutin.

(och här ser man ju förresten den "snygga" 111^2 = 12321)