[pe-e-be]

Ada algoritma yang pake fungsi logaritma untuk setiap titik ketika rendering, mengingat fungsi logaritma lambatnya minta ampun.

salah satu algoritma yang gw temukan untuk menghitung logaritma melibatkan pembagian iteratif dalam 2 tahap dan pembagian adalah AFAIK operasi aritmetika sederhana yang perlu cpu cycle paling mahal (dibanding perkalian)

kira-kira dari solusi di bawah (tambahin klo belum ada) lebih baik pilih yang mana dan kenapa? thx b4

- SLUT (simply look up table)?
- Algoritma numerik yang lebih cepat (pake binary log atau fixed point number)?
- program di gpu?

[L_O_J]

dari yang paling mudah menurut gue sih:

- LUT
- GPU
- Algo baru


Masalah yang paling baik, menurut gue trade off. LUT IMO yang paling gak tepat tapi paling cepet.

[pe-e-be]

klo mo pake LUT mesti tau batasan memori jg kayaknya. klo mo per-bit bisa sampe 4GB (IEEE 754) buat LUT.

barusan dapet algoritma berbasis LUT yang cuma pake 64K memori dan presisi sampe 1e-7. setelah gw benchmark (di CPU), lumayan 4 kali lebih cepat.

vinyals, Oriol; et al. Revisiting Basic function on current CPUs: A fast logarithm implementation with adjustable accuracy. June 21, 2007. ICSI Berkeley Report

gw pake 16 bit mantissa (jadi 7 bit dibuang) dan implementasiin untuk log10 (bukan ln).

var
 //16 bit used for mantissa lookup
  lut               : array[0..65535] of single;
//IEEE 754 32-bit Floating-Point Number

procedure precalc_lut;
var
  step              : integer;
  i, p, x           : integer;
  fval              : single;
  pf                : ^dword;

begin
  pf := @fval;
  x := $3F800000;
  pf^ := x;
  step := 1 shl 16;//23 - 7
  p := 1 shl 7;
  for i := 0 to p - 1 do begin
    lut[i] := log2( fval );
    x := x + step;
    pf^ := x;
  end;
end;

function _log10( val: single ): single; register;
var
  pf                : ^dword;
  x, log_2        : integer;
begin
  pf := @val;
  x := pf^;
  log_2 := ( ( x shr 23 ) and $FF ) - 127;
  x := (x and $7FFFFF) shr 16;
  result := ( 
  ( lut[x] 
  + log_2 
  ) 
  * 0.301029995664 
  );
end;

klo yang GPU gimana lil?

[Kiki]

hehehe ... mo nimbrung ... bikin fungsi logaritma pake SSE, masalahnya :

1. nggak gitu akurat, maklum cuma evaluasi maclaurin series cuma 4 suku saja
2. Only work for x where 0 < x < 2 (open interval)
3. No guarantee it is faster

ini kodenya :

#include <cstdio>
#include <cmath>
#include <xmmintrin.h>



float maclaurin(float val){
	__declspec(align(16) ) float tmp[4] = { 1.0F,1.0F,1.0F,0.0F};
	__declspec(align(16) ) float multiplier[4] = { 1.0F,-0.5F,0.33333333F,-0.25F};
	tmp[3] = val;
	__m128 vec1 = _mm_load_ps(tmp);
	__m128 vec2 = _mm_shuffle_ps( vec1,vec1,0xF4);
	__m128 vec3 = _mm_shuffle_ps( vec1,vec1,0xFC);
	__m128 vec4 = _mm_shuffle_ps( vec1,vec1,0xFF);
	__m128 acc  = _mm_mul_ps(vec1, vec2);
	acc  = _mm_mul_ps(acc, vec3);
	vec1 = _mm_load_ps(multiplier);
	acc  = _mm_mul_ps(acc, vec4);
	acc  = _mm_mul_ps(acc,vec1);
	vec1 = _mm_shuffle_ps(acc,acc, 0xE4);
	vec2 = _mm_shuffle_ps(acc,acc, 0x39);
	vec3 = _mm_shuffle_ps(acc,acc, 0x4E);
	vec4 = _mm_shuffle_ps(acc,acc, 0x93);
	acc  = _mm_add_ps(vec1,vec2);
	acc  = _mm_add_ps( acc, vec3);
	acc  = _mm_add_ps(acc, vec4);
	float res;
	_mm_store_ss(&res,acc);
	return res;
}

float my_log(float x){
	return maclaurin(x - 1);
}

int main(){
	float reference = logf(1.3F);
	float target    = my_log(1.3F);
	printf(" reference = %g , target = %g\n", reference, target);
}

di komputer gw, outputnya :

reference = 0.262364 , target = 0.261975

not bad ...

[L_O_J]

Wogh maap om peb, otak gue cuman nyampe ke LUT, yang GPU sama Algo baru mah gue asumsi dari tingkat kesulitannya, maksudnya creating a new faster algo itu jelas lebih sulit daripada utilize GPU toh . kalo coding GPU om kiki noh .

[Kiki]

Originally Posted by L_O_J

kalo coding GPU om kiki noh .

kok gw ? biar GPU itu mesin SIMD, kl tiap elemennya cuma integer 8 bit, gw bisa apa ? (nggak pernah make floating point format)