Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Amenintat cu moartea de un numar ...

La multi ani @AndReW99!

Alegere masina £15000 uk

TVR vrea sa lanseze o platforma d...
 Strategie investie pe termen lung...

Modulator FM ptr auto alimentat p...

orange cablu f.o. - internet fara...

Robinet care comuta traseul
 A fost lansata Fedora 40

Samsung S24 plus

Imi iau un Dell? (Vostro vs others)

Abonati Qobuz?
 transport -tren

Platforma electronica de eviden&#...

Cot cu talpa montat stramb in per...

Sfat achizitie sistem audio pentr...
 

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,950
  • Î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,235
  • Î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,453
  • Î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,235
  • Î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,235
  • Î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,453
  • Î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,235
  • Î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,437
  • Î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

Chirurgia spinală minim invazivă Chirurgia spinală minim invazivă

Chirurgia spinală minim invazivă oferă pacienților oportunitatea unui tratament eficient, permițându-le o recuperare ultra rapidă și nu în ultimul rând minimizând leziunile induse chirurgical.

Echipa noastră utilizează un spectru larg de tehnici minim invazive, din care enumerăm câteva: endoscopia cu variantele ei (transnazală, transtoracică, transmusculară, etc), microscopul operator, abordurile trans tubulare și nu în ultimul rând infiltrațiile la toate nivelurile coloanei vertebrale.

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