[alg] kleinst grotere macht van 2

[Zoijar]

Ik heb nu een functietje die voor een geheel getal n de kleinste macht van 2 vind die groter gelijk is aan n. Dus bv voor 24 krijg je 32, voor 4 krijg je 4, voor 5, 8 etc.

Maar volgens mij doe ik het naief, dwz ik deel steeds n door 2 totdat er geen rest is en daarbij vermenigvuldig ik het antwoord elke stap met 2. Complexiteit is dus O(log n) ... dat moet toch wel beter kunnen? Ik wil/kan alleen niet met bitjes toveren, dus geen bit magic antwoord Oh en bovendien heb ik geen Log functie.

[Tim Schuhmacher]

Ik heb niet precies door wat je aan het doen bent, maar ken je 'mod' (modulo) en 'div'

5 mod 2 = 1
5 div 2 = 2

Te gebruiken voor '... ik deel steeds n door 2 totdat er geen rest is..'
Of denk ik nu te simpel?

[ Voor 62% gewijzigd door Tim Schuhmacher op 15-03-2003 12:54 ]

[Zoijar]

oh, ja die functie die ik beschreef heb ik wel al, maar ik zocht dus een andere snellere manier.

Wat ik dus heb:

code:

nearestPow2 n = nearestPow2' (n-1) 1
nearestPow2' 0 x = x 
nearestPow2' n x = nearestPow2' (n/2) (x*2)

Kan sneller/beter?

[ Voor 47% gewijzigd door Zoijar op 15-03-2003 13:00 ]

[zeroxcool]

Ik denk dat je bezig bent met priemgetallen, is het niet?

[Zoijar]

ZeRoXcOoL schreef op 15 March 2003 @ 13:00:
Ik denk dat je bezig bent met priemgetallen, is het niet?

Min of meer, het vermenigvuldigen van 2 (hele grote) getallen in O(n log n), mbv een FFT. Daarvoor moet ik de lengte van een vector aanpassen zodat die een macht van 2 is. Ik werk verder wel modulo een priem getal, maar dat staat los van m'n vraag

[ACM]

En zoiets?
x = ceil(y / 2) * 2
?

Maar dat van jou ziet er niet echt imperatief uit, kent je taal een ceil functie?
Dat heb je dus eigenlijk al, alleen dan recursief?

[ Voor 20% gewijzigd door ACM op 15-03-2003 13:08 ]

[drm]

Maar dan zit je toch alsnog met een complexiteit van de ceil functie (die dus eigenlijk onbekend is) Als 't hier daadwerkelijk om de complexiteit van de functie gaat is het niet echt handig met andere functies aan te komen waarvan die onbekend is, of begrijp ik 't nou verkeerd

[Zoijar]

ACM schreef op 15 March 2003 @ 13:04:
En zoiets?
x = ceil(y / 2) * 2
?

Maar dat van jou ziet er niet echt imperatief uit, kent je taal een ceil functie?
Dat heb je dus eigenlijk al

Functionele taal ja ... en nee heb ook geen ceil. Maar dat werkt toch ook niet? ceil(14 / 2) * 2 = 14 en niet 32. Dat is het kleinst groter gelijke even getal.

[Zoijar]

drm schreef op 15 March 2003 @ 13:09:
Maar dan zit je toch alsnog met een complexiteit van de ceil functie (die dus eigenlijk onbekend is) Als 't hier daadwerkelijk om de complexiteit van de functie gaat is het niet echt handig met andere functies aan te komen waarvan die onbekend is, of begrijp ik 't nou verkeerd

Ja precies. Op zich is O(log n) niet slecht, maar kan het niet in constante tijd?

[ACM]

ceil(14 / 2) *2 is volgens mij 16...
Ownee,
de ceil van de 2 log nemen...

sorry
Algoritme's zijn dan ook niet mijn sterkste kant

[ Voor 60% gewijzigd door ACM op 15-03-2003 13:13 ]

[drm]

Ik zit ff te puzzelen maar ik kan ook geen betere bedenken... Theoretisch ben ik dan ook niet zo geweldig onderlegd in dit soort dingen, dus verlies je hoop niet

---

edit:

Ik bedenk me trouwens dat 't uberhaupt niet anders kan, volgens mij, want de enige andere referentie die je hebt is een lagere macht van 2, en dan zit je met 'tzelfde probleem.... Hoewel je met bits misschien nog een eind zou kunnen komen, maar dat wilde je niet

En als je zou gaan kijken door welke macht van 2 je kunt delen verhoog je de complexiteit alleen maar
[/brainstorm]

[ Voor 56% gewijzigd door drm op 15-03-2003 13:21 ]

[Zoijar]

drm schreef op 15 March 2003 @ 13:18:
Ik zit ff te puzzelen maar ik kan ook geen betere bedenken... Theoretisch ben ik dan ook niet zo geweldig onderlegd in dit soort dingen, dus verlies je hoop niet

---

edit:

Ik bedenk me trouwens dat 't uberhaupt niet anders kan, volgens mij, want de enige andere referentie die je hebt is een lagere macht van 2, en dan zit je met 'tzelfde probleem.... Hoewel je met bits misschien nog een eind zou kunnen komen, maar dat wilde je niet

En als je zou gaan kijken door welke macht van 2 je kunt delen verhoog je de complexiteit alleen maar
[/brainstorm]

Ja ik denk ook dat ik hier aan vast zit. Aangezien de "x `pow` n" functie in de taal zelf ook van complexiteit O(log n) is. Ik heb wel is een manier in constante tijd gezien met bitmagic, maarja heb ik dus niks aan

[Verwijderd]

Is er een bepaalde reden waarom je geen bitshifts wil gebruiken of biedt het taaltje waarin je werkt geen bitshifts, en indien dat laatste, weet je dat wel heel zeker? Of wacht, je getallen zijn waarschijnlijk zo groot dat ze niet in een 32-bits register passen en je daarom niet van dat soort operaties erop kan toepassen?

Waarschijnlijk zijn al de andere operaties als vermenigvuldingen en delen ook O(log n) operaties, dus onder O(log n) tijd kom je dus niet uit. Het voorbeeld dat je hierboven gegeven hebt zou dan ook wel eens O(loglog n) kunnen zijn.

[ Voor 62% gewijzigd door Verwijderd op 15-03-2003 14:37 ]

[PiepPiep]

Als je getal niet in een 32 bits register past heb je zelf waarschijnlijk een class/struct geschreven om je getallen bij te houden.
Heb je daar niet een getalletje in met hoelang het getal is?
Als je namelijk je grote getal opdeelt in 32 bits integers en je hebt een getal van 234 keer een 32 bits integer dan hoe je alleen de most significant 32bits integer te converten naar zo'n hogere 2 macht en zet je de rest op 0
voorbeeld
most significante 32 bits integer is 0x00341283
wordt
most significante 32 bits integer is 0x00400000
de rest van de 32 bits integers worden dan 0

[EfBe]

met bits freubelen is vele malen sneller, maar het is wel erg gefreubel: origineel getal de meest linkse bit vinden (significant bit) die 1 is. Die 1 naar links shiften. Klaar. (rest 0). Maar die individuele bittests zijn niet te voorkomen. Op zich is bij grote getallen het zeker vele malen sneller (dus de pieppiep methode van hierboven) dan de deling die TS toepast.

[Verwijderd]

Maar die individuele bittests zijn niet te voorkomen.

Dit betekent dat je dus al meer dan log n tests moet doen en je dus eigenlijk al een log n algoritme hebt.

[Sjaaky]

Vanaf de 386 is er een instructie die de plek van het meest significante bit in een register teruggeeft. Maar dat is niet echt te gebruiken in een functionele taal.

[.oisyn]

Je kunt steeds shiften en or'en, dan heb je in principe een algo dat in constante tijd op te lossen is

Stel je hebt x = 00100101
Als je die or'd met (x >> 1), dan krijg je dus x' = 00110111
Als je die weer or'd met (x' >> 2), dan krijg je x'' 00111111
In principe ben je er nu al, maar de volgende zou worden: (x'' >> 4), en daarna (x''' >> 8 ), etc.
Daar kun je dan simpelweg 1 bij optellen, en dan krijg je 01000000

Het aantal shifts dat nodig is is in principe log (aantal bits in getal), maar dat weet je van tevoren natuurlijk niet, maar als je uitgaat van een 32 bits getal is er dus 5 shifts en ors nodig

Nadeel is echter wel dat een macht van 2 ook naar boven afgerond wordt (en dus met 2 vermenigvuldigd). Misschien is er een handige manier om daarop te checken of dat teniet te doen?

(voor het aantal bits in een getal is ook een snel algo beschikbaar, dus als je dat erop toepast, en daar komt 1 uit, kun je het onveranderd laten)

[ Voor 11% gewijzigd door .oisyn op 15-03-2003 21:36 ]

[.oisyn]

Mijn suggestie wordt zeg maar zoiets dus: (in C++ weliswaar, maar daar weet je wel raad mee neem ik aan )

C++:

int bitcount (unsigned n)
{
    static const unsigned MASK_01010101 = 0x55555555;
    static const unsigned MASK_00110011 = 0x33333333;
    static const unsigned MASK_00001111 = 0x0f0f0f0f;

    n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ; 
    n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ; 
    n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ; 
    return n % 255 ;
}

unsigned pow2ceil (unsigned x)
{
    if (bitcount (x) == 1)
        return 1;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;
}

[ Voor 23% gewijzigd door .oisyn op 15-03-2003 22:06 ]

[PiepPiep]

Sjaaky schreef op 15 maart 2003 @ 20:38:
Vanaf de 386 is er een instructie die de plek van het meest significante bit in een register teruggeeft. Maar dat is niet echt te gebruiken in een functionele taal.

_{offtopic
Welke is dat dan?}

[Sjaaky]

BSR—Bit Scan Reverse
Description
Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand). The source operand can be a register or a memory location; the destination operand is a register. The bit index is an unsigned offset from bit 0 of the source operand. If the contents source operand are 0, the contents of the destination operand is undefined.

[ACM]

Zoijar schreef op 15 March 2003 @ 12:46:
Ik wil/kan alleen niet met bitjes toveren, dus geen bit magic antwoord

Lezen is lastig, oisyn?

[.oisyn]

ACM schreef op 16 March 2003 @ 13:19:
Lezen is lastig, oisyn?

misschien was het niet helemaal duidelijk, maar ik haakte in op de opmerkingen van PiepPiep en EfBe

goed, op zich kun je de deling van Zoijar wel wegwerken door alleen vermenigvuldigingen te gebruiken, maar hij blijft O (log n)

code:

nearestPow2 n = nearestPow2' 1 n
nearestPow2' x n
|(x >= n)   = x
|otherwise  = (x * 2) n

[Varienaja]

nearestPow2 x = 2^RondOmhoogAf(²log x)

Kweet alleen niet of je taaltje 'log' kent. (In mijn miranda-boek kan ik niks vinden).

[ Voor 21% gewijzigd door Varienaja op 17-03-2003 13:00 ]

[.oisyn]

Oh en bovendien heb ik geen Log functie

[Varienaja]

.oisyn schreef op 17 March 2003 @ 13:03:
[...]

Ohja

Als je onder de complexiteit van log n uit wilt komen kan je extra geheugen declareren.

MachtenVanTwee = [ x^2 | x<-[1..32] ]

nearestPow2 x = hd [ y | y<-machtenVanTwee; y>=x ]

^{Kut, ik geloof dat je dan nog steeds complexiteit van Log n hebt...}

[ Voor 17% gewijzigd door Varienaja op 17-03-2003 13:09 ]

[Peetman]

PiepPiep schreef op 15 maart 2003 @ 22:49:
[...]

_{offtopic
Welke is dat dan?}

BSR of BSF

[Apollo_Futurae]

Zoijar schreef op 15 March 2003 @ 12:57:

code:

nearestPow2 n = nearestPow2' (n-1) 1
nearestPow2' 0 x = x 
nearestPow2' n x = nearestPow2' (n/2) (x*2)

Kan sneller/beter?

sneller waarschijnlijker niet. als je taal haskell is, kan het wel netter:

code:

nearestPower base n = until (>= n) (* base) 1

p.s.:
jouw code die ik hierboven gequote heb klopt niet: hugs geeft voor nearestPow 2 een getal van tientallen decimalen

[Zoijar]

Apollo_Futurae schreef op 17 maart 2003 @ 18:55:
[...]
sneller waarschijnlijker niet. als je taal haskell is, kan het wel netter:

code:

nearestPower base n = until (>= n) (* base) 1

p.s.:
jouw code die ik hierboven gequote heb klopt niet: hugs geeft voor nearestPow 2 een getal van tientallen decimalen

De code die ik gaf is voor Gofer, werkt goed.

Ik heb het er maar bij gelaten, de rest van het algoritme is toch al O(n log n). Bovendien ligt 'n' rond de 4096; wat dit power verhaal een factor 0,00024 maakt op het totaal Ik vroeg het me gewoon af vanuit theoretisch oogpunt.

[Soultaker]

Apollo_Futurae schreef op 17 maart 2003 @ 18:55:
sneller waarschijnlijker niet. als je taal haskell is, kan het wel netter:

code:

nearestPower base n = until (>= n) (* base) 1

Ik werk zelden met Haskell, maar in de functionele talen die ik ken is dit een typisch voorbeeld van verkeerd gebruik van de argumenten van infix operatoren. Je moet bedenken dat in ">= n" die n het eerste argument van de >= operator is en dat resulterende functie toegepast op x dus "n >= x" zal zijn.

Je zult dus ofwel expliciet de argumenten om moeten wisselen:

Clean:

nearestPower base n = until (flip (>=) n) ((*) base) 1

Ofwel de andere vergelijking moeten gebruiken:

Clean:

nearestPower base n = until (f(<) n) ((*) base) 1

Of natuurlijk while in plaats van until gebruiken, maar dan wijzigt de conditie ook:

Clean:

nearestPower base n = while ((>) n) ((*) base) 1

Ik gebruik extra haakjes om de operatoren omdat dat in Clean noodzakelijk is (en in andere talen geen kwaad kan, vermoed ik).

Wat betreft de complexiteitsdiscussie: hoeveel lager dan O(log N) dacht je te komen? O(log (log N)) of iets dergelijks is een zeldzaamheid; met een eenvoudige constructie zul je misschien wel op een constante tijd kunnen komen (nog beter natuurlijk). Daarvoor is echter ofwel een lookup-table nodig (niet echt gewenst hier, denk ik), ofwel functies die het hoogste bit uitrekenen of logaritmen uitrekenen. Lookup-tables zijn trouwens toch al problematisch in veel functionele talen.

Als je N rond de 1000 ligt, is de constante factor in je algoritme trouwen veel interessanter dan de theoretische complexiteit en sich. Dat is ook de reden dat een worst-case O(N^2) algoritme als quicksort (dat gemiddeld natuurlijk wel O(N log N) is) heel vaak wordt verkozen boven O(N log N) sorteeralgoritmen.

[ Voor 22% gewijzigd door Soultaker op 17-03-2003 20:50 ]