Board.KolibriOS.org

Official KolibriOS board
It is currently Wed Oct 23, 2019 9:38 pm

All times are UTC+03:00




Post new topic  Reply to topic  [ 19 posts ]  Go to page 1 2 Next
Author Message
PostPosted: Sun Apr 10, 2011 10:39 am 
Offline
User avatar

Joined: Tue Aug 25, 2009 4:45 pm
Posts: 796
1. Библиотеки, для работы с большими числами:

bigshit

biglib


Attachments:
File comment: BigLib
biglib.zip [20.94 KiB]
Downloaded 175 times
File comment: bigshit
bigshit09.zip [11.06 KiB]
Downloaded 174 times
Top
   
PostPosted: Sun Sep 11, 2011 3:41 pm 
Примеры конечно интересные, но больно уж накручено. Вот бы что-то попроще и помельче. Начать что ли свою библиотеку подобную Box_Lib и Proc_Lib. Единственный минус, что мне сейчас реально нужна бывает только процедура деления. Остальное и выделять то в библиотеку смешно как-то. В самом деле не будешь же выделять простейшее imul eax,ebx, а вот с делением приходится повозиться и тащить в каждую программу кусок вроде нижеприведенного:
Spoiler: Show
Code:
integer_division:
; eax = eax/ebx
   test   ebx,ebx
   jnz   @f
   inc   ebx
@@:
   xor   edx,edx
   div   ebx
   shl   edx,1
   cmp   ebx,edx
   jb   @f
   inc   eax
;@@:
   ret

Иногда просто хочется иметь простенькие и достаточно эффективные процедуры математики без задействования FPU. Тем более что в некоторых случаях он оказывается слабоватым, к примеру в eBox из-за этого проигрывание видео тормозится, да время расчета с использованием FPU не всегда гарантировано. В общем как воздух нужна библиотека лишенная этих недостатков.


Top
   
PostPosted: Sun Sep 11, 2011 8:16 pm 
Offline
User avatar

Joined: Mon Apr 16, 2007 6:38 pm
Posts: 1222
Mario, я думаю, что при вызове библиотеки ради одного-двух таких кусочков, накладные расходы больно большими получаются. Ну а ежели таких кусков много используется (в том числе и более сложных), тогда уже да... В свою очередь предлагаю написанный мной алгоритм извлечения квадратного корня добавить в такую библиотеку, ежели кто займëтся оной:

Spoiler: Show
Code:
sqrt: ;24 code (not comments) strings
;in: eax-number; out: ebx-result of fullnumber sqrt,
; if eax wasn't changed, ebx is ideal result, else:
; ecx-(bigger-ideal), eax-(ideal-smaller);
; result is bigger than floatpoint if ecx<eax, else smaller;
; to find percentage, b=ecx/(ecx+eax), s=eax/(ecx+eax):
; ((b>>0)=>b is nearly to ideal, for s is same; always<1)
cmp eax,0
jne @f
    xor ebx,ebx
    ret
@@:
mov ebx,-1
xor ecx,ecx
@@:
    add ebx,2
    add ecx,ebx
cmp ecx,eax
je @f ; we don't need to find nearly result, ecx is this.
jb @b
;now: ecx-bigger square, (ecx-ebx)-smaller, eax-ideal;
;need: check, what square mostly near to input number.
    sub ecx,eax
    mov eax,ebx
    sub eax,ecx ; eax=ebx-(ecx-eax)=eax-(ecx-ebx)=ideal-smaller.
    cmp ecx,eax ; cmp(bigger-ideal,ideal-smaller).
    jb @f ; ecx mostly near.
    sub ebx,2 ; it will be incremented soon, so lets annihilate this.
;crushed: eax; now: ecx,eax-see header.
@@: ; ecx is better
    inc ebx
shr ebx,1
ret


функция довольно неплохая, на мой взгляд, я потратил на неë довольно много времени

_________________
И мы уже давно не пешки,
Мы пули, мы орлы, и решки!
Война ютит бинарный код,
Умри, или иди вперед!


Top
   
PostPosted: Sun Sep 11, 2011 8:44 pm 
Gluk wrote:
Mario, я думаю, что при вызове библиотеки ради одного-двух таких кусочков, накладные расходы больно большими получаются. Ну а ежели таких кусков много используется (в том числе и более сложных), тогда уже да...

Ну, так собственно потому я и расплывался мыслью по древу по посту - ради одной функции это бессмысленно.
Gluk wrote:
В свою очередь предлагаю написанный мной алгоритм извлечения квадратного корня добавить в такую библиотеку, ежели кто займëтся оной:

Вот за это спасибо! Еще бы реализовать синус.


Top
   
PostPosted: Sun Sep 11, 2011 9:12 pm 
Offline

Joined: Mon Sep 24, 2007 11:11 am
Posts: 2814
А табличный метод не подходит?


Top
   
PostPosted: Sun Sep 11, 2011 9:15 pm 
Табличный метод ограничен размерами памяти.


Top
   
PostPosted: Sun Sep 11, 2011 9:20 pm 
Offline

Joined: Mon Sep 24, 2007 11:11 am
Posts: 2814
Нужно в float или пойдет int в виде sin (x) * 100, к примеру? Какая точность нужна? Каких углов?


Top
   
PostPosted: Sun Sep 11, 2011 9:37 pm 
Offline
User avatar

Joined: Mon Apr 16, 2007 6:38 pm
Posts: 1222
sin*255 мне видится логичнее, для одного байта

_________________
И мы уже давно не пешки,
Мы пули, мы орлы, и решки!
Война ютит бинарный код,
Умри, или иди вперед!


Top
   
PostPosted: Sun Sep 11, 2011 9:45 pm 
И как мы потом будем скрещивать ужа с ежом? ЯВУ код с асм кодом подружить в одной *.obj библиотеке проблематично.
Насчет точности не знаю пока.


Top
   
PostPosted: Sun Sep 11, 2011 9:58 pm 
Offline

Joined: Mon Sep 24, 2007 11:11 am
Posts: 2814
Можно и на ассемблере ведь. Быстро и экономично, мне кажется, так:
1) Создание таблицы для 90*n значений (точность зависит от n), расчет через примитивное разложение x-(x^3)/6+(x^5)/120...
Займет, допустим, 360*n байт памяти - не так уж и накладно
2) Затем линейное интерполирование (прям из книжки пример)
x1 = x*(количество_значений_в_массиве)/pi
y1 = (элемент_массива_номер_x1)
y2 = (элемент массива_номер_x1+1)
Синус = y1 + (y2-y1)*(x*(количество значений в массиве)/pi-x1)
Точность будет, скорее всего, достаточная. И зависеть будет от первого пункта - насколько точно разложили в ряд и сколько элементов в таблицу положили. И скорость будет хорошая.


Top
   
PostPosted: Sun Sep 11, 2011 11:40 pm 
Offline
Kernel Developer

Joined: Wed Mar 08, 2006 6:25 pm
Posts: 3952
а FPU не катит ?


Top
   
PostPosted: Mon Sep 12, 2011 12:14 am 
Я уже имел счастье наблюдать, что на eBox таки хреново катит FPU.


Top
   
PostPosted: Mon Sep 12, 2011 1:04 am 
Offline
User avatar

Joined: Tue May 08, 2007 12:44 am
Posts: 346
Извините, что встреваю, могу рассказать баян. В FastMM для Delphi видел классную функцию CardinalToStrBuf, обходящуюся без деления вообще:
Spoiler: Show
Code:
{Converts a cardinal to string at the buffer location, returning the new
 buffer position. Note: Only supports numbers up to 2^31.}
function CardinalToStrBuf(ACardinal: Cardinal; APBuffer: PAnsiChar): PAnsiChar;
asm
  {On entry: eax = ACardinal, edx = ABuffer}
  push edi
  mov edi, edx                //Pointer to the first character in edi
  {Calculate leading digit: divide the number by 1e9}
  add eax, 1                  //Increment the number
  mov edx, $89705F41          //1e9 reciprocal
  mul edx                     //Multplying with reciprocal
  shr eax, 30                 //Save fraction bits
  mov ecx, edx                //First digit in bits <31:29>
  and edx, $1FFFFFFF          //Filter fraction part edx<28:0>
  shr ecx, 29                 //Get leading digit into accumulator
  lea edx, [edx + 4 * edx]    //Calculate ...
  add edx, eax                //... 5*fraction
  mov eax, ecx                //Copy leading digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #2}
  mov eax, edx                //Point format such that 1.0 = 2^28
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 28                 //Next digit
  and edx, $0fffffff          //Fraction part edx<27:0>
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #3}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:27>
  lea edx, [edx * 4 + edx]    //5*fraction, new fraction edx<26:0>
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 27                 //Next digit
  and edx, $07ffffff          //Fraction part
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #4}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:26>
  lea edx, [edx * 4 + edx]    //5*fraction, new fraction edx<25:0>
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 26                 //Next digit
  and edx, $03ffffff          //Fraction part
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #5}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:25>
  lea edx, [edx * 4 + edx]    //5*fraction, new fraction edx<24:0>
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 25                 //Next digit
  and edx, $01ffffff          //Fraction part
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #6}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:24>
  lea edx, [edx * 4 + edx]    //5*fraction, new fraction edx<23:0>
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 24                 //Next digit
  and edx, $00ffffff          //Fraction part
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #7}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:23>
  lea edx, [edx * 4 + edx]    //5*fraction, new fraction edx<31:23>
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 23                 //Next digit
  and edx, $007fffff          //Fraction part
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #8}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:22>
  lea edx, [edx * 4 + edx]    //5*fraction, new fraction edx<22:0>
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 22                 //Next digit
  and edx, $003fffff          //Fraction part
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #9}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:21>
  lea edx, [edx * 4 + edx]    //5*fraction, new fraction edx<21:0>
  cmp ecx, 1                  //Any non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 21                 //Next digit
  and edx, $001fffff          //Fraction part
  or ecx, eax                 //Accumulate next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store digit out to memory
  {Calculate digit #10}
  lea eax, [edx * 4 + edx]    //5*fraction, new digit eax<31:20>
  cmp ecx, 1                  //Any-non-zero digit yet ?
  sbb edi, -1                 //Yes->increment ptr, No->keep old ptr
  shr eax, 20                 //Next digit
  or eax, '0'                 //Convert digit to ASCII
  mov [edi], al               //Store last digit and end marker out to memory
  {Return a pointer to the next character}
  lea eax, [edi + 1]
  {Restore edi}
  pop edi
end;

Тип Cardinal в Delphi -- это DWORD.

_________________
Разработчик языка программирования Кантор


Top
   
PostPosted: Mon Sep 12, 2011 1:15 am 
Offline
Kernel Developer

Joined: Wed Mar 08, 2006 6:25 pm
Posts: 3952
Mario
Там и целочисленные тормозить будут, если сравнивать с K8+ и P6+.
Надо смотреть точность алгоритмов, а то эта математика насчитает...


Top
   
PostPosted: Mon Sep 12, 2011 3:45 pm 
Offline
Kernel Developer
User avatar

Joined: Thu Sep 03, 2009 1:52 pm
Posts: 1621
Товарищи, среди нас тайный агент ЯВУшников! Только он мог предложить такой алгоритм, чтобы ЯВУшники смогли показать на http://hackersdelight.org/HDcode/isqrt.c.txt и применить один из своих любимых доводов "ассемблерщики слишком заняты мелкими проблемами вместо того, чтобы использовать более сложные, но более быстрые алгоритмы".


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 19 posts ]  Go to page 1 2 Next

All times are UTC+03:00


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited