[WISK] breuken vereenvoudigen

[Verwijderd]

wat is nu de beste manier om breuken te vereenvoudigen,

stel : breuk a/b
moet men controleren welke var de kleinste is (in dit geval zullen we even stellen dat dit a is)
dan kijken welke priemgetallen er allemaal zijn tussen 1-a, en vervolgens kijken door welk van deze priemgetalen a en b kunnen worden gedeeld
goed plan, maar het lukt dus niet, want er is geen formule (heb ik toch gelezen) die de priemgetallen van 1-x kan berekenen

dan dacht ik
neem a (nog steeds gesteld dat dit het kleinste getal is)
en deel a en b door 1,2,3,...,a
en kijk zo bij welke getallen dit zal lukken, is wel een aardige manier denk ik
maar bij zeer grote getallen is dat vrij zwaar om te berekenen

nu is mijn vraag, zijn er beter alternatieven, of heb ik in mijn uitleg iets over het hoofd gezien

GruBen

[Verwijderd]

Rekensommetjes zijn voor computers van tegenwoordig easy, daar zijn ze immers voor gemaakt en de Mhz'en die ons tegenwoordig tot beschikking staan voldoet voor zulke dingen wel. Ik zou dus gewoon het kleinste getal van de twee nemen en van 1-a met net zo lang delen tot het niet meer kan, zoals dat ook op de basisschool gebeurde...

Wellicht dat er een efficiëntere oplossing is, dat zou natuurlijk mooier stan, maar ik zou me geen zorgen maken over grote getallen..

[Verwijderd]

opgelet
het is de bedoeling om een wiskundig programma te maken dat zo efficient mogelijk zou werken, stel dat je een 10^7 hebt moet er dus 10^7 maal een lus worden doorlopen
dat loopt wel op

dus ik vraag me af, kan dit niet effcienter

[Apache]

waarom moet er 10^7 maal de lus doorlopen worden?

in dat simpel geval toch maar zoveel keer als de exponent?

[Verwijderd]

als het getal bjvoorbeeld 1458878995564545 is, dan moeten al de mogelijkheden toch worden afgegaan, of zie ik het verkeerd

[Verwijderd]

Ahh, volgens mij is dit een studie-opdracht

[Verwijderd]

niet echt
we vervelen ons wat id vakantie, en zijn van plan een wiskundeprogramma te schrijven

niemand een idee
ik bedacht juist, ik moet dus eigenlijk de grootste geme deler van de twee getallen vinden, niet

iemand daar een algoritme voor?

[Verwijderd]

Jah, ff denken hoor, gaat op dit tijdstip niet echt vlot meer
Ehhh, als ie te vereenvoudigen is, dan is volgens mij het kleinste getal altijd de grootste gemene deler... of denk ik nu te makkelijk

[Verwijderd]

okok
hartelijk bedankt iedereen, ik denk dat ik een algoritme heb gevonden

[Verwijderd]

Will u show it us? Of het programma?

[Verwijderd]

simpelweg het algoritme van euclides gebruikt
is snel te vinden met google,
maar ik was er dus niet opgekomen dat om een breuk te vereenvoudigen de ggd nodig is

[Alarmnummer]

hoe zijn jullie van plan om die rekenmachine van invoer te voorzien? Je zou het kunnen doen met knopjes, maar das wel vrij ouderwets. Het is een stuk leukers als je gewoon tekst kan invoeren, hij parsed het even en daarna evalueert hij als er geen parse fouten zijn. Op http://www.antlr.org staan genoeg tutorials om dit voor elkaar te krijgen. Ik ben zelf ook begonnen met antlr, en het is een hele leuke parser generator en makkelijk om mee te werken. Er staan trouwens een paar voorbeelden in het pakket, waarmee je al bijna een kant en klare expressie parser klaar hebt. Het is wel niet geavanceerd, maar goed genoeg om mee te oefenen

[Verwijderd]

dat is dus nog allemaal een vraag
we zijn er nog helemal niet uit hoe dat in zen werk gaat gaan

we zijn nu nog in het stadium van de algebraïsche en analytische zaken in orde te brengen en te zorgen dat dit alles correct werkt

maar idd daar moet nog eens goed over worden nagedacht

[Alarmnummer]

hmmzz.. ik heb zelf intussen wel redelijk ervaring op dit gebied. Misschien is het handig als jullie je theoretische informatica boek (of iets in die geest) er bij pakken zodat je al die leuke expressie bomen weer voor de geest hebt.

Met een expressie boom heb je op een hele elegantie manier beschikking over je ingevoerde formules en kan je er hele leuke transformaties op loslaten, waaronder een evaluatie.

Ik denk dat dit de meest handige manier is om dit aan te gaan pakken.

succes er in ieder geval mee, en zo nu en dan de vooruitgang even posten

[Verwijderd]

jah,

we zijn nog maar net begonnen, er is al een plotfunctie voorhanden enzo, en nu zijn we met de algebra bezig
binnen een maand, anderhalf maand, wordt het projectje opensource (gpl waarschijnlijk), en dan kan je de ontwikkelingen od voet volgen

[Alarmnummer]

Ik ben trouwens wel benieuwd hoe jullie jullie expressie hebben opgeslagen, want als je hem gaat plotten, ga je hem dus evalueren.

[Verwijderd]

sleepy me

[Alarmnummer]

Jullie gebruiken een plotfunctie van maple? Of jullie gebruiken maple om jullie expressies in op te slaan?

[Juup]

Is het nou ook de bedoelinf dat je een uitdrukking als dit vereenvoudigt:

code:

 5x-11      3      2
-------- = ---  + ---
x^2-5x+4   x-4    x-1

Of werk je alleen met getallen?

[ Voor 0% gewijzigd door Juup op 04-08-2002 11:07 . Reden: format ]

[windancer]

Het algoritme van Euclides is inderdaad de oplossing. Als je de "brute force" methode zou willen gebruiken hoef je trouwens maar de getallen 1,2,3,..sqrt(a) te doen. Als je dan nog geen deler hebt zul je er ook geen vinden.

Verwijderd schreef op 04 augustus 2002 @ 03:13:
wat is nu de beste manier om breuken te vereenvoudigen,

stel : breuk a/b
moet men controleren welke var de kleinste is (in dit geval zullen we even stellen dat dit a is)
dan kijken welke priemgetallen er allemaal zijn tussen 1-a, en vervolgens kijken door welk van deze priemgetalen a en b kunnen worden gedeeld
goed plan, maar het lukt dus niet, want er is geen formule (heb ik toch gelezen) die de priemgetallen van 1-x kan berekenen

dan dacht ik
neem a (nog steeds gesteld dat dit het kleinste getal is)
en deel a en b door 1,2,3,...,a
en kijk zo bij welke getallen dit zal lukken, is wel een aardige manier denk ik
maar bij zeer grote getallen is dat vrij zwaar om te berekenen

nu is mijn vraag, zijn er beter alternatieven, of heb ik in mijn uitleg iets over het hoofd gezien

GruBen

[Verwijderd]

Je kunt truuks toepassen:
-even getallen zijn deelbaar door priemgetal 2,
-getallen waarbij alle digits bijelkaar opgeteld deelbaar is door 3 is deelbaar door 3

Net zolang doordelen door 2 totdat a en/of b niet meer even zijn, plus / of de 3 truuk toepassen levert al veel kleinere getallen op voor a en b. Daarna euclides toepassen levert een aardig efficient algoritme op. Priemgetallen opzoeken is wel een heidens karwei en vziw is daar geen algoritme voor.

[whoami]

Otis schreef op 04 augustus 2002 @ 12:29:
Je kunt truuks toepassen:
-even getallen zijn deelbaar door priemgetal 2,
-getallen waarbij alle digits bijelkaar opgeteld deelbaar is door 3 is deelbaar door 3

Net zolang doordelen door 2 totdat a en/of b niet meer even zijn, plus / of de 3 truuk toepassen levert al veel kleinere getallen op voor a en b. Daarna euclides toepassen levert een aardig efficient algoritme op. Priemgetallen opzoeken is wel een heidens karwei en vziw is daar geen algoritme voor.

Waarom zou je eerst doordelen door 2 of de '3-truuk' toepassen? Ik vermoed dat het efficienter zal zijn om direct de ggd te gaan bepalen en dan de noemer en de teller door die ggd te gaan delen. Het bepalen van de ggd is nu ook zo zwaar rekenkundig niet.

_{Hoezo geen algoritme om priemgetallen te gaan bepalen? Er is voor alles wel een algoritme te vinden/schrijven...}

[Alarmnummer]

En als je de grootste gemeenschappelijke deler van n wilt zoeken, hoef je maar te gaan tot roundUp(wortel(n)) te gaan, aangezien a*b = b*a Scheelt je ook al weer de helft.

[edit]
ik zie dat windancer dat ook al had verteld

[Verwijderd]

whoami schreef op 04 augustus 2002 @ 13:22:
[...]
Waarom zou je eerst doordelen door 2 of de '3-truuk' toepassen? Ik vermoed dat het efficienter zal zijn om direct de ggd te gaan bepalen en dan de noemer en de teller door die ggd te gaan delen. Het bepalen van de ggd is nu ook zo zwaar rekenkundig niet.

de ggd bepalen van kleinere getallen is efficienter dan voor grotere getallen. Je kunt dus dan je efficiency vergroten door veel voorwerk al te doen. Je moet toch een serie priemgetallen 'proberen' in euclides' algoritme. Het resultaat los je daarna wel op, maar bij kleinere getallen is het veelal niet meer dan 2 of 3 slagen.

_{Hoezo geen algoritme om priemgetallen te gaan bepalen? Er is voor alles wel een algoritme te vinden/schrijven...}

Het bepalen van priemgetallen is vziw een kwestie van databases met getallen aflopen en niet een rekenkundig iets. Wil je bv alle priemgetallen weten tussen 100 en 1000, dan zul je alle producten van getallen < 100 uit die lijst moeten vissen en met de rest die je overhoudt ga je kijken of ze deelbaar zijn door de getallen < 500. Het is wel een 'algoritme', maar niet zoeen die lineair een rijtje getallen langsfietst en een paar berekeningen uitvoert (althans, niet dat ik weet)

[Verwijderd]

Zoek de GCD (Greatest Common Divider) van a en b op.
Deel vervolgens a en b door die GCD.

Doe dit net zolang tot GCD == 1

[edit]
formule voor GCD komt eraan, paar minuutjes

[Verwijderd]

gcd(a,b) = a if a = b
gcd(a,b) = 2 x gcd(a/2,b/2) if a even, b even
gcd(a,b) = gcd(a/2,b) if a even, b odd
gcd(a,b) = gcd(a,b/2) if a odd, b even
gcd(a,b) = gcd(a-b,b) if a odd, b odd, a > b
gcd(a,b) = gcd(a,b-a) if a odd, b odd, a < b

Dit moet je binair implementeren.

[Verwijderd]

Voorbeeldje:

gcd(308₁₀,182₁₀) =
gcd(100110100₂,10110110₂) =
2 x gcd(10011010₂,1011011₂) =
2 x gcd(1001101₂,1011011₂) =
2 x gcd(1001101₂,1110₂) =
2 x gcd(1001101₂,111₂) =
2 x gcd(1000110₂,111₂) =
2 x gcd(100011₂,111₂) =
2 x gcd(11100₂,111₂) =
2 x gcd(1110₂,111₂) =
2 x gcd(111₂,111₂) =
2 x 111₂ =
1110₂ =
14₁₀

[windancer]

En nu met de algoritme van Euclides :

(308, 182) 308 mod 182 = 126
(182,126) 182 mod 126 = 56
(126, 56) 126 mod 56 = 14
(56, 14) 56 mod 14 = 0

dus 14 is de GCD.

[Verwijderd]

Het algoritme van Euclides was ik inderdaad ff vergeten.

Komt door een prakticum met powerpc assembler wat ik vorige week afgemaakt heb

[RickN]

whoami schreef op 04 augustus 2002 @ 13:22:
[...]
_{Er is voor alles wel een algoritme te vinden/schrijven...}

Halting-problem

[Verwijderd]

idd het is onmogelijk om alle priemgetallen te vinden tussen 1 en x

[Verwijderd]

nog een vraagje

ik ben van plan met variabelen te werken die verschillende toestanden kunnen aannemen, zoals scalars in perl

hoe heet dit soort variabelen officieel, zodat ik eens fatsoenslijk kan opzoeken hoe dit best te implementeren valt

[Alarmnummer]

Ik heb net even gekeken wat een scalar in perl is, en wat ik heb begrepen is dat het variable is waarin dus een waarde kan staan, een hashmap met waardes of een array. Een type dat zich kan gedragen als type 1, of als type2 of als type2 heet een union of variant type. Het type van de variable is dus van dat type.

Als je iets meer over wilt weten, moet je deze maar eens doorkijken:
http://research.microsoft...Papers/TypeSystems.A4.pdf
http://research.microsoft...rs/OnUnderstanding.A4.pdf

[MSalters]

Verwijderd schreef op 04 augustus 2002 @ 12:29:
Je kunt truuks toepassen:
-getallen waarbij alle digits bijelkaar opgeteld deelbaar is door 3 is deelbaar door 3

Truc werkt niet op compu's. 111(bin)=7(dec) is niet deelbaar door 3. De truc voor 11(dec) werkt mutatis mutandis wel voor 11(bin)=3(dec), tel alle bits op even posisties en alle bits op oneven posities. Als het verschil even is, dan is het getal deelbaar door 3.
Dus 00111001 heeft 3 bits op even posities , en 1 on oneven, en is dus deelbaar door 3 (check: 57/3=19)

[RickN]

Verwijderd schreef op 05 augustus 2002 @ 00:09:
idd het is onmogelijk om alle priemgetallen te vinden tussen 1 en x

MMM, knipoog. Is dit een valstrik reply??? En als ik er nu op reageer sta ik zeker voor lul ofzo?? Nou ja, whatever:

Het is niet onmogelijk alle priemgetallen tussen 1 en x te vinden. Da's zelfs heel makkelijk en er is een zeer bekend eeuwenoud algoritme voor: Eratosthenes Sieve.

Algoritme draait in O(x log log x), dus niet lineair.

-Er is geen algoritme bekend dat in lineaire tijd de eerste N priemgetallen genereerd.
-Er is geen algortime bekend dat in O(N) bepaald (met 100% zekerheid) of N een priemgetal is.

[Verwijderd]

MSalters schreef op 05 augustus 2002 @ 08:01:
[...]
Truc werkt niet op compu's. 111(bin)=7(dec) is niet deelbaar door 3. De truc voor 11(dec) werkt mutatis mutandis wel voor 11(bin)=3(dec), tel alle bits op even posisties en alle bits op oneven posities. Als het verschil even is, dan is het getal deelbaar door 3.
Dus 00111001 heeft 3 bits op even posities , en 1 on oneven, en is dus deelbaar door 3 (check: 57/3=19)

DIgits als in:

27, digits: 2 en 7. Bijelkaar optellen: 9. 9 mod 3 is 0. -> deelbaar door 3. Werkt dus wel degelijk op een computer.

Geen binaire digits, ik heb nergens genoemd dat ik over een ander talstelsel sprak dan het 10 tallige.