Scenergy #02
31 декабря 1999

Coding - 16-битная процедура быстрого возведения в степень.

                    FAST 16-bit SQUARE ROOT

This  is  nice,  but what about arbitrary numbers which are not
powers of two? Fortunatelly, there is nice trick which allows us
to look at arbitrary number this way:

X = 2^N * M

Where:
N is number of bits needed to represent number X
M is mantissa of X and lies in interval <0, 1>

Thinking this way, we can say:

128 = 2^8 * 0.5
 40 = 2^6 * 0.625

 Since  we  are  experienced  in  mathematics  [are we?], we can
calculate sqrt(X) easily:

sqrt(X) = 2^(N/2) * sqrt(M)

For example:

sqrt(144) = sqrt(2^8 * 0.5625) = 2^4 * sqrt(0.5625) =
= 2^4 * 0.75 = 12

 Voila!  It  works!  Let's  summarize  it  and write square root
algorithm:

  1) Find out N [number of bits we need to represent number X].
  2) Calculate mantissa M.
  3) Take sqrt(M) from table.
  4) Take N/2 highest bits from mantissa to get result.

 One may ask how do we calculate the mantissa. Answer is simple.
We just take highest 8 bits of number X [highest 8 bits does not
mean  higher byte!]. Then we make one lookup to SQRT table which
is built this way:

for i = 0 to 255
  SQRT[i] = 256 * sqrt(i / 256)

 Few  more  questions  appear.  Is 8 bits enough? Is square root
stored  with  enough  precision?  Yes.  Since we are calculating
square  root  of  16-bit number, result will be surely 8-bit. In
addition,  sqrt(M)  is even bigger number than M [but still lies
in  interval <0, 1>]. Smart reader can also ask: "What if N will
be  odd?  How  we  half it then?". Again, solution is simple. We
will take nearest higher value as N. For example:

24 = 2^5 * 0.75 => 2^6 * 0.375

 That's  all  about  basis  of  this  method.  Now  we can start
developing routine. The main trick is to put highest 8 bits of X
into  one byte to take mantissa [as these bits can lie partly in
higher  byte  and  partly  in  lower  byte  of X]. I solved this
problem  by  set  of tables. First table shifts higher byte of X
into leftmost position. Few examples should make it clear:

01 -> 10 ... shifted left 4 times
                ^
00110101 -> 11010100 ... shifted left 2 times
                  ^^
0110 -> 110 ... shifted left 5 times
               ^
 Now  we  need just to add few highest bits from lower byte of X
at  highlighted positions. This is done by set of masking tables
[there  are eight of them; each will return 0-7 highest bits for
given number]. Let me show some examples:

Table 3

1 -> 0111 ... three highest bits
10100110 -> 0101
^^^
Table 5

1 -> 0001 ... five highest bits
10011010 -> 00010011
^

 This  table  set can be also used to get final N/2 highest bits
from mantissa. Of course, we must somehow remember how many bits
we  shifted left, because we must know how many bits to add from
lower byte. This is where next table come from. For each shifted
number  it  contains  pointer to related masking table. I am not
going  to  confuse  you  with  more explanations, so look at the
final code:

BC - number to proccess

 ld      h,SHIFT       ; we are going to shift higher byte of X
 ld      l,b
 ld      a,(hl)        ; shift it!
 inc     h
 ld      b,(hl)        ; get pointer to N/2 masking table
 inc     h
 ld      h,(hl)        ; get pointer to masking table
 ld      l,c
 or      (hl)          ; add lower bits [calculate the mantissa]
 ld      h,SQRT
 ld      l,a
 ld      c,(hl)        ; get square root of mantissa
 ld      a,(bc)        ; get N/2 highest bits from mantissa

 Summa  summarum,  76T and just 3K of tables. Would you ever say
that  this  linear  piece  of  code  can perform square root? Of
course,  some  extremists [those like me] can save another 3T by
changing  "ld h,SQRT" to "inc h" and having SQRT table stored in
memory  several  times. It is upon you to decide if 3T are worth
of additional 2K. Oh! I forgot table generator, so you will have
to  make  it  by  yourself.  It will help you to understand this
method  better  and  maybe  you  will  find  something even more
usable. Happy coding!

  -baze-3SC->



Другие статьи номера:

A.O.S.S. - "Сцена больна" переживания Random'a.

A.O.S.S. - Raver рассуждает о сценовой журналистике.

A.O.S.S. - аналитическая статья о музыкальной сцене от Andy Fer.

A.O.S.S. - легко ли быть органайзером группы?

A.O.S.S. - О журналах (мысли вслух).

A.O.S.S. - о канонах демосцены на примере журнала Deja Vu #9.

A.O.S.S. - Сегодня и Завтра отечественной демосцены.

A.O.S.S. - спектрумовская банерная сеть.

Charts - all time favorites.

Charts - current rules (fall edition 1999).

Charts - indexed.

Charts - voting rules.

Coding - 16-битная процедура быстрого возведения в степень.

Coding - Flying представляет макробиблиотеку: Memory Management Library.

Coding - Texture Mapping - реализация от SaiR00S/EI.

Coding - Texture mapping + Phong shading реализация от Senat/Eternity Industry.

Coding - ZXA library: библиотека, предназначенная для создания и проигрывания анимаций.

Coding - Баг в STS?

Coding - Комментарии к исходникам, опубликованным в Scenergy #1

Coding - о библиотеках в программировании на спектруме.

Coding - Принцип упаковки анимаций в демо JAM.

Coding - процедура быстрого умножения.

Coding - разбор интро Daingy от Cryss/Razzlers.

Demo Party - Cafe'2000: Официальное приглашение

Demo Party - CC999.999 information (eng).

Demo Party - D-Man/EI: отчет о Di:Halt:99.

Demo Party - Hartman: отчет о CC'999.

Demo Party - Maxwell и Mr. John: отчет о CC'999.

Demo Party - Merlin/CC: отчет о CC'999.

Demo Party - Paradox'99 - как это было, но лучше б он mUst dIe!!!

Demo Party - PHAT'9: список посетителей.

Demo Party - POL/PHT: отчет о Doxycon '99.

Demo Party - Random/CC: обьемный отчет о CC'999.

Demo Party - SerzhSoft: сказание о CC'999.

Demo Party - Zlincon 2e3 party: минирепортаж.

Demo Party - информация о предстоящем пати PHAT'0.

Demo Party - информация по демопарти CC999.999.

Demo Party - неофициальные результаты Di:Halt'99 с коментариями Diver'a.

Demo Party - обзор демосцены за 1999 год.

Demo Party - отчет организаторов CAFe'99.

Demo Party - пресс релиз Латвийского демопати PHAT'9.

Demo Party - приглашение на латвийское демопати PHAT'9.

Demo Party - рассказ о поездке Antares в Казань на CAFe'99

Demo Party - результаты CC.999.999

Demo Party - результаты CC999.999.

Demo Party - результаты Chaos Construction 999.

Demo Party - результаты Computer Art Festival 1999.

Demo Party - результаты Doxycon'99.

Demo Party - результаты Millenium Party.

Demo Party - результаты Paradox'2k demoparty.

Demo Party - результаты Латвийского демопати PHAT'9.

Demo Party - результаты Ростовского пати Paradox'99.

Demo Party - репортаж Gasman'a с Forever 2e3.

Demo Party - репортаж с Минского демопати Millennium'2000.

Demo Party - финальные результаты Forever 2E3.

Editorial - вступительное слово от Arty.

Editorial - выступительное слово от Random.

Editorial - загоны Raver'а на тему Сцены.

Groups - анкеты действующих групп: Amaltiya Incoropration Software.

Groups - анкеты действующих групп: Antares.

Groups - анкеты действующих групп: Ascendancy Creative Labs.

Groups - анкеты действующих групп: Crushers.

Groups - анкеты действующих групп: E-mage.

Groups - анкеты действующих групп: Eternity Industry.

Groups - анкеты действующих групп: Excess team.

Groups - анкеты действующих групп: Extreme Entertainment.

Groups - анкеты действующих групп: Fatality.

Groups - анкеты действующих групп: Jupiter 77.

Groups - анкеты действующих групп: Proxima Centauri.

Groups - анкеты действующих групп: RaZZLeRs.

Groups - анкеты действующих групп: RUSH.

Groups - анкеты действующих групп: Smash Hackers Band.

Illegal Corner - Razzlers оправдываются за релиз демки First Association.

Illegal Corner - Scenergy Release Charts - конкурс крэков.

Illegal Corner - Welcome to Scenergy Release Charts (SRC).

Illegal Corner - софтография Fatality Group.

Lits - Pussy: история создания знаменитой игры от Fatality.

Lits - Scenergized beyond the belief.

Lits - speed.

Lits - история образования Ростовской ассоциации PartyZans.

Lits - история создания игры "Белый орел - товарищ известен".

Lits - рассказ о том как Fatality выпускает игрушки.

Mail Box - письма: Ellvis и Fatality довольны Scenergy #1, Ulterior поносит Antares и BrainWave, Realtimer разочарован.

News - Doom'a не будет!

News - Виртуальное пати Millennium, X-Raizor вернулся на сцену, Andrew Fer организовал новую группу, провал Германского пати Spectrology, новости от 3SC, Zero Team, Extreme.

News - мнение Megus'a о dentro compo СС'2000.

News - новости от OHG, Delta Hackers Group, Die Crupps, Волгодонских спектрумисто и от группы SpeedWay.

Scenergy - адреса для связи с редакцией.

Scenergy - благодарности соавторам журнала.

Scenergy - новое в облочке журнала.

Scenergy - обещанного видео в статьях не будет...

V.I.P. - Random берет интервью у Unbel!ever/Sage/XTM.

V.I.P. - The most noble tale of the scene.

V.I.P. - интервью с Arny и Mythos, создателями клона Elite игры Awaken.

V.I.P. - Интервью с Fatality, широко известными крэкерами и гейм-мэйкерами

V.I.P. - интервью с одним из авторов игры Elite.

V.I.P. - интервью с одним из самых прогрессивных художников на спектруме Diver/4D.

V.I.P. - Интервью, взятое у Random'а каким-то PC-журналом

Warez Pack - описание Inertia Player.

Warez Pack - описание демо 1140.

Warez Pack - описание импортной демки 'no work'.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Вступление - 13 годовщина газеты...
Почтовый ящик - дискуссия.
Программирование - Вывод 64 символов в строке.

В этот день...   2 июня