Code golf challenge: logaritm

[•Cosmin]

http://infoarena.ro/blog/code-golf-logaritm

[•klamathix]

Facem o cautare binara gen Patrascu dar continuam si pe puterile negative ale lui 2, pe care le calculam scotand radical in mod succesiv din 2. sper ca e ok, n-am avut timp sa o testez acum.

[•Cosmin]

Pai ii zice code golf pt ca trebuie si codul .

[•klamathix]

yup, scuze, nu eram atent. sunt in ora de germana:)) am sa bag si cod.

[•cristi8]

Cod:

typedef double d;
#define r return
d l(d x){d s=1e-5,S=6931e-9+1;if(fabs(x-1)<5e-5)r 0;if(x>1)r x>=2?l(x/2)+1:l(x/S)+s;r x<=.5?l(x*2)-1:l(x*S)-s;}

LE: (thanks rgrig)

Cod:

#define r return
double l(double x){if(fabs(x-1)<5e-5)r 0;if(x>1)r x>=2?l(x/2)+1:l(x/(6931e-9+1))+1e-5;r -l(1/x);}

[•MciprianM]

96 caractere; din pacate nu merge decat pentru x > 1.

Cod:

double log(double x){double p,r=1.0000105766425498,t;for(p=0,t=r;t<x;p+=1,t*=r);return p/65536;}

[•rgrig]

MciprianM: Simpatica solutia. Uite o varianta recursiva (care merge si pentru x < 1):

Cod:

typedef double d;d e=1.0000105766425498;d L(d x, d a){return x<1?-L(1/x,a):x<e?a:L(x/e,a+1./65536);}

Se apeleaza cu L(x,0) si trebuie compilata cu optimizarea tail-call-ului ca sa nu dea stack-overflow. (Cu gcc asta inseamna -O2 sau mai sus.)

Edit: Am schimbat l in L ca la fonturile astea se confunda cu 1.
Edit2: Uitasem typedeful.
Edit3: Uite si o varianta in Haskell. COnstanta e un pic mai scurta dar cred ca merge.

Cod:

e=1.0000105766425
f x a|x<1= -f(1/x)a|x<e=a|True=f(x/e)(a+1/65536)

[•Cosmin]

Misto! Ati sarit direct la variantele obfuscate, puteti baga si explicatii la solutii?

[Update1]
Eu am doua, dar nu am pus efort sa le fac scurte.

Prima e pe ideea de care vorbea Mihai mai sus. La fiecare pas incerc sa aflu o cifra in baza 2 a rezultatului.

Cod:

def log_base2(y):
  if y < 1:
    return -log_base2(1/y)

  p = 2.0
  e = 1.0
  while p * p <= y:
    p *= p
    e *= 2
  x = 0
  res = 1
  while e > 1e-10:
    if res * p <= y:
      res *= p
      x += e
    p = math.sqrt(p)
    e /= 2

  return x

Un coleg de echipa a venit cu o idee mai scurta, el foloseste faptul ca ln(x) ~= x - 1 pentru x foarte apropiat de 1 si proprietatea ca ln(x) = 2 * ln(sqrt(x)).

Cod:

def ln(x):
  if x < 1.0:
    return -xlog(1/x)
  if x > 1 + 1e-9:
   return 2*ln(math.sqrt(x))
  return x - 1

def log(x):
  return ln(x) / 0.69314718

[Update2]
A 2-a solutie scrisa mai scurt in Python are 85 de caractere 'non whitespace':

Cod:

import math
def l(x):
  return x < 1 and -l(1/x) or (x > 1+1e-9 and 2*l(math.sqrt(x)) or (x - 1) / .693147)

[Update3]
93 de caractere daca nu numaram 'white space' in C++, 77 fara include math:

Cod:

#include <math.h>
double L(double x){return(x<1?-L(1/x):(x>1+1e-9?2*L(sqrt(x)):(x-1)/.693147));}

[•MciprianM]

In solutia mea, r este 2^(1/65536), iar p este logaritm in baza r din x. Adica r^p=x adica logaritm in baza 2 din x e p/65536.

P.S.: Precizia e de 4 zecimale pt ca 65536 > 10000. Ca sa ajung la solutia mea de la faptul ca raspunsul poate fi scris ca fractie zecimala cu 4 cifre sau ca p/10000, unde p e intreg. am folosit 65536 pentru ca 2^(1/65536) e mai usor de calculat decat 2^(1/10000) (faci radical de radical de radical ... din 2).

Edit:

Mie imi  place solutia cu ln(x)=2ln(sqrt(x)) si ln(x)=x-1 pt x apropiat de 1 - e geniala. Din pacate am auzit destul de multi oameni care ziceau chestii de genu': daca ii problema de mate eu nu o stiu face. De-aia imi place solutia asta. Omul care foloseste solutia asta nu se teme de mate si cred ca ar trebui promovata mai mult gandirea matematica la info. Tin minte ca la noi la liceu se preda algoritmul cu planificarea spectacolelor (ala din capitolul greedy din Cormen) fara demonstratie. Adica profesorul le zicea ca solutia e asa: sortati intervalele de timp in care se pot tine spectacolele dupa terminare si apoi luati greedy intervalele. Fara sa se explice de ce merge (ca de-aia se fac demonstratii, nu? ca sa se observe ca ii adevarata o teorema - in cazul nostru ca algoritmul functioneaza sau ca are timpul de executie nu stiu cat si nu stiu cate altele). Si alti algoritmi erau tratati la fel (imi vin in minte acuma aia de grafuri: Kruskal, Dijkstra, ...).

Cred ca se intelege ca vreau sa zic ca matematica nu promoveaza invatarea algoritmilor pe de rost ci intelegerea lor, nu?

[•blustudio]

Solutia mea, desi contine ceva mai multe caractere decat cele postate anterior, adica 115 cu whitespace, se bazeaza pe ideea ca integrala din 1/x dx este ln(x). Astfel putem foarte usor face asta destul de precis, metode mai bune fiind regulile lui Simpson, dintre care este recomandata Simpson 3/8. Stiu ca este foarte lenta pt. numere mai mari, dar imi place deoarece este foarte simpla.

Cod:

#define d double
d l(d x){d a=min(1.0,x);x=max(1.0,x);d r=0;while(a<x){r+=1/a*1e-6;a+=1e-6;}if(x-1<1e-6)r*=-1;return r;}

Codul curat si un exemplu de folosire:

Cod:

#include <cstdio>
#include <algorithm>
using namespace std;

double ln(double x)
{
	double dx = min(1.0, x);
	x = max(1.0, x);
	double result = 0.0;
	while (dx < x)
	{
		result += 1 / dx * 1e-6;
		dx += 1e-6;
	}
	if (x < 1)
		result *= -1;
	return result;
}

int main()
{
	float x;
	printf("x = ");
	scanf("%f", &x);
	printf("ln(%f) = %f\n", x, ln(x));
	return 0;
}

O alta solutie ce mi-a venit in minte este bazata pe derivata lui a^x, dupa cum este cunoscut (a^x)' = a^x * ln(a). Codul bazat pe aceasta idee se afla mai jos si are 76 de caractere.

Cod:

double f(double x){return (pow(x,2.0+1e-6)-pow(x,2.0))/1e-6/pow(x,2.0+1e-7);}

Codul curat si un exemplu de utilizare:

Cod:

#include <cstdio>
#include <cmath>

double ln(double x)
{
	double df = pow(x, 2.0 + 1e-6) - pow(x, 2.0);
	double dx = 1e-6;
	double f = pow(x, 2.0 + dx / 2);
	return (df / dx) / f;
}

int main()
{
	float x;
	printf("x = ");
	scanf("%f", &x);
	printf("ln(%f) = %f\n", x, ln(x));
	return 0;
}

Edit: Acum am vazut ca nu am voie sa folosesc functia putere asa ca am adaptat ultima solutie sa foloseasca radical de ordinul doi pentru a obtine o putere rationala de ordinul 1e-6. Codul sub aceasta forma este mai jos.

Cod:

double ln(double x)
{
	double rx = x;
	for (int i = 1; i <= 20; i++)
		rx = sqrt(rx);
	double df = x * x * rx - x * x;
	double dx = 1 / (double)(1 << 20);
	return (df / dx) / (x * x * sqrt(rx));
}