Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Divorț la notar

Vechime vs km reali

Android 12 : "Yahoo Mail s-a ...

Bloc Favorit cu RS2
 Ce extractor audio (analogic) pen...

Cine suporta cheltuielile de jude...

Apartament Grecia - Kavala

obtinere venituri PFA / PFI in ti...
 Recomandare Volvo

Diferenta suprafata teren

Plafonare preturi energie

Vanzari foto - CIPA 2023
 Recomandare perdele sau draperii ...

Invertor Victron Easysolar-II 48/...

"Militarizarea" Antifraudei

Washington DC in 1940 - secvente ...
 

Algoritm calculare ridicare la putere?

- - - - -
  • Please log in to reply
12 replies to this topic

#1
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
Algoritm calculare ridicare la putere:
am cautat mult algoritmi rapizi pentru ridicarea la putere: baza/exponent;
Intr-un final am gasit asta:
http://szhorvat.net/...-of-powers.html
am implementa metoda recursiva asa:
int power_impl_rec(int x, unsigned int e)
{
if (e==0) return 1;
if (e==1) return x;
		if (e%2 == 0)
			return power_impl_rec(x*x, e>>1);
		else if (e%3 == 0)
			return power_impl_rec(x*x*x, e/3);
		return power_impl_rec(x, e-1)*x;
}

Am incercat sa o convertesc fara suces in forma iterativa:
int power_it(int x, unsigned n)
{
if (n==0) return 1;
if (n==1) return x;
// initialize result by 1
int pow = 1;
// do till n is not zero
while (n>1)
{
  if (n%2 == 0)
  {
  n = n >> 1;
  x = x*x;
  }
  else if (n%3 == 0)
  {
  n = n / 3;
  x = x*x*x;
  }
  else
  {
  n--;
  // Aici este problema
  // x = power_it(x, n)*x;
  }

}
// return result
return x;
}


Deci cum pot sa repar metoda iterativa???
A doua intrebare chiar merita/ va fi foarte rapida comparativ cu metoda clasica???
int power_clasic(int x, unsigned n)
{
// initialize result by 1
int pow = 1;
// do till n is not zero
while (n)
{
  // if n is odd, multiply result by x
  if (n & 1)
   pow *= x;
  // divide n by 2
  n = n >> 1;
  // multiply x by itself
  x = x * x;
}
// return result
return pow;
}

????

#2
sags

sags

    Senior Member

  • Grup: Senior Members
  • Posts: 9,753
  • Înscris: 24.04.2013
Sa zicem ca stabilesti un invariant pentru functia ta, de exemplu (purPosted Image exemplu) ca rezultatul final cautat este egal cu pow · xn.
  • dupa declararea lui pow este respectat fiindca vrei xn si ai setat pow = 1.
  • daca este respectat la inceputul unei iteratii si esti in cazul n par, atunci invariantul ramane respectat si dupa operatiile din if-il respectiv in baza egalitatii pow · xn = pow · (x2)(n/2).
  • simiar daca n este multiplu de 3 (partea cu else if)
  • acum vezi tu cum faci sa actualizezi cele 3 variabile, n, x si pow, pentru cel de al treilea caz…
  • … si ce trebuie sa intorci la sfarsit, avand in vedere ca din ciclu se iese cu n = 1.


#3
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,111
  • Înscris: 24.02.2007
Sa masuram, dar cu numere mari (clasa mea de aici https://forum.softpe...de/page__st__18 nu tocmai rapida)

3 la puterea 123:
  • power_clasic 173685 ns
  • power_impl_rec  63948 ns

n = n >> 1 se poate scrie linistit n /= 2. Stie compilatorul sa faca operatii pe biti daca ii se cer optimizari.

Edited by dani.user, 25 February 2020 - 20:27.


#4
parabellum

parabellum

    Senior Member

  • Grup: Senior Members
  • Posts: 2,439
  • Înscris: 06.01.2010
// Aici este problema

Nici o problema, adaugi acolo:
pow *= x;

La return:
return pow * x;

Doar am aruncat o privire rapida peste cod, s-ar putea sa gresesc.

#5
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
@parabellum: Multumesc.

Versiunea revizuita:
//http://szhorvat.net/pelican/fast-computation-of-powers.html
int power_it(int x, unsigned n)
{
if (n==0) return 1;
// initialize result by 1
int pow = 1;
// do till n is greather then 1
while (n>1)
{
  if (n&1 == 0)
  {
  n = n >> 1;
  x = x*x;
  }
  else if (n%3 == 0)
  {
  n = n / 3;
  x = x*x*x;
  }
  else
  {
  n--;
  pow *= x;
  }
}
// return result
return pow * x;
}



#6
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,111
  • Înscris: 24.02.2007
Ai nevoie de viteza mai mare pentru ridicat int la puteri? La cat e de mic un int se calculeaza repede si cu varianta simpla.

#7
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016

Quote

Ai nevoie de viteza mai mare pentru ridicat int la puteri?
Stiu ca un int nu poate stoca mai mult de 2^31.
Pentru numere mari exista alti algoritmi.

Exista inca o problema cu codul anterior, lipsa unor paranteze rotunde:
if ((n&1) == 0)  // if n divisible to 2
  {
...
else if ((n%3) == 0)  // if n divisible to 3
  {
...

// https://codegolf.stackexchange.com/questions/32254/determine-if-an-integer-is-divisible-by-3
// This is ~5/6x times faster then clasic n%3
// But still 1 second slower then i>>1 (which is around 5 seconds);
inline int IsDivisibleBy3(int n)
{
return (n * 0xAAAAAAAB)<=n;
}

Am observat ca n%3 este destul de incet.

Pentru impartire la 3:
inline int FastDivBy3_short(int n)
{
return (((unsigned int)n * (unsigned int)0xAAAB) >> 17);
}
doar ca metoda short nu functioneaza decat pentru valori de 16 biti.

Versiunea "full"
unsigned int divby3(unsigned int divideMe)
{
	return (unsigned int)((0xAAAAAAABLL * divideMe) >> 33);
}
Doar ca acesta utilizeaza long long, rezultatul calcul neincapand in unsigned int.
Versiunea long long este de 3x ori mai slaba ca divideMe/3.
Cu alte cuvinte nu stiu nici un algoritm mai eficient ca divideMe/3,
pe cand pentru n%3 exista.

#8
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,111
  • Înscris: 24.02.2007
https://godbolt.org/z/to5Lem

Cum ziceam, compilatorul e mai destept decat il credem.

#9
parabellum

parabellum

    Senior Member

  • Grup: Senior Members
  • Posts: 2,439
  • Înscris: 06.01.2010

Quote

Exista inca o problema cu codul anterior, lipsa unor paranteze rotunde:
Nu si la %, acolo e ok si fara paranteze, precedenta e mai mare decat la ==.

#10
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
Intr-un final am gasit:
https://www.overcloc...code-speedup!!!

int power_clasic2(int x, unsigned n)
{
// initialize result by 1
int t = 1;
if (n<=32)
{
  switch (n)
  {
  
			case 0: t = 1; break;
			case 1: t = x; break;
			case 2: t = x*x; break;
			case 3: t = x*x*x; break;
			case 4: t = x*x*x*x; break;  // OLD CODE: t = b*b; t*=t; 
			case 5: t = x*x; t*=t; t*=x; break;  // 2^2*2^2*2^1 = 2^5
			case 6: t = x*x*x; t*=t; break;  // 2^3*2^3 = 2^6
			case 7: t = x*x*x; t*=t; t*=x; break;  // 2^3*2^3*2^1 = 2^7
			case 8: t = x*x; t*=t; t*=t; break;	// (2^2)*(2^2) => 2^4*2^4 => 2^8
			case 9: t = x*x; t*=t; t*=t; t*=x; break;
			case 10: t = x*x; t*=t; t*=x; t*=t; break;
			case 11: t = x*x; t*=t; t*=x; t*=t; t*=x; break;
			case 12: t = x*x*x; t*=t; t*=t; break;  // first 2^3
			case 13: t = x*x*x; t*=t; t*=t; t*=x; break;
			case 14: t = x*x*x; t*=t; t*=x; t*=t; break;
			case 15: t = x*x*x; t*=t; t*=x; t*=t; t*=x; break;  // last 2^3
			case 16: t = x*x; t*=t; t*=t; t*=t; break;
			case 17: t = x*x; t*=t; t*=t; t*=t; t*=x; break;
			case 18: t = x*x; t*=t; t*=t; t*=x; t*=t; break;
			case 19: t = x*x; t*=t; t*=t; t*=x; t*=t; t*=x; break;
			case 20: t = x*x; t*=t; t*=x; t*=t; t*=t; break;
			case 21: t = x*x; t*=t; t*=x; t*=t; t*=t; t*=x; break;
			case 22: t = x*x; t*=t; t*=x; t*=t; t*=x; t*=t; break;
			case 23: t = x*x; t*=t; t*=x; t*=t; t*=x; t*=t; t*=x; break;
			case 24: t = x*x*x; t*=t; t*=t; t*=t; break;
			case 25: t = x*x*x; t*=t; t*=t; t*=t; t*=x; break;
			case 26: t = x*x*x; t*=t; t*=t; t*=x; t*=t; break;
			case 27: t = x*x*x; t*=t; t*=t; t*=x; t*=t; t*=x; break;
			case 28: t = x*x*x; t*=t; t*=x; t*=t; t*=t; break;
			case 29: t = x*x*x; t*=t; t*=x; t*=t; t*=t; t*=x; break;
			case 30: t = x*x*x; t*=t; t*=x; t*=t; t*=x; t*=t; break;
			case 31: t = x*x*x; t*=t; t*=x; t*=t; t*=x; t*=t; t*=x; break;
  
	  }

return t;
}
else
{
// do till n is not zero
while (n)
{
  // if n is odd, multiply result by x
  if (n & 1)
   t*= x;
  // divide n by 2
  n = n >> 1;
  // multiply x by itself
  x = x * x;
}
return t;

}
}


power_clasic2 este de aproape doua ori mai rapid decat power_clasic pentru puteri mai mici de 32,
pentru valori mai mari ca 32 rezultatul oricum nu incape intr-un unsigned int.

#11
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,111
  • Înscris: 24.02.2007
Merita deranjul pentru doar de 2x mai rapid?

#12
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016

Quote

Merita deranjul pentru doar de 2x mai rapid?
Asta depinde de cat de mult utilizezi functia de ridicare la putere.
Daca utilizezi o singura data acea functie/fara a fi in bucle - de fapt nu vei sesiza nici o diferenta, nici chiar daca rulezi functia clasica,
timpul de executie fiind foarte foarte mic.

Voi incerca pe viitor sa implementez ceva pentru ridicare la putere numere mari.

Apropo:
double B = log(x);
double C = n*B;
double A = exp(C);
Asta functioneaza dar din pacate returneaza valoare aproximativa a lui x^n.

#13
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,295
  • Înscris: 10.08.2005
si unde vrei sa pastrezi rezultatul asta extrem de mare ?


View PostIvanMihai, on 08 martie 2020 - 11:38, said:

power_clasic2 este de aproape doua ori mai rapid decat power_clasic pentru puteri mai mici de 32,
pentru valori mai mari ca 32 rezultatul oricum nu incape intr-un unsigned int.

Edited by MarianG, 08 March 2020 - 23:25.


Anunturi

Neurochirurgie minim invazivă Neurochirurgie minim invazivă

"Primum non nocere" este ideea ce a deschis drumul medicinei spre minim invaziv.

Avansul tehnologic extraordinar din ultimele decenii a permis dezvoltarea tuturor domeniilor medicinei. Microscopul operator, neuronavigația, tehnicile anestezice avansate permit intervenții chirurgicale tot mai precise, tot mai sigure. Neurochirurgia minim invazivă, sau prin "gaura cheii", oferă pacienților posibilitatea de a se opera cu riscuri minime, fie ele neurologice, infecțioase, medicale sau estetice.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate