Getal berekenen ipv voluit noteren

[Skit3000]

Hoi!

Stel dat je een getal van 100 tekens lang hebt als:
987654321234567890120987654323456765456787654678987654323456789234567654567654678909876543456789087

Weet iemand of er een methode bestaat om een som samen te stellen die korter is dan 100 tekens maar wel op dit getal uit komt? Ik heb al wat foefjes geprobeerd met worteltrekken / delen / vermenigvuldigen maar ik kom daarmee nooit precies op het oorsponkelijke getal uit (als ik de getallen achter de komma weglaat; als ik die er bij haal lukt het wel maar dan is mijn som veel langer dan het originele getal).

Andere methode die ik heb geprobeerd, is om een getal van 100 tekens te laten genereren, om vanuit daar te vermenigvuldigen met 100,1111111111111111111% of 99,9999999999999999% afhankelijk van het verschil tussen het oorspronkelijke nummer en het berekende getal, om zo een hoger of lager nummer te krijgen. Hierbij noteerde ik een binaire 1 als het hoger was, of een binaire 0 als het lager was en zette dat daarna om in het 10-tallig stelsel. Hierbij liep ik tegen de limieten op van de standaard lengte van Int/Float in veel programmeertalen, maar toen ik BigInt implementaties ging gebruiken bleek dat ook dit veel meer "som" op te leveren dan de oorsponkelijke lengte van het getal.

Heeft iemand anders nog slimme ideeën om zoiets voor elkaar te krijgen?

[Knuckless]

Omzetten naar hexadecimaal?

[Soultaker]

Wat mag er precies in je som gebeuren?

Om een kortere som te maken heb je operaties nodig die uit twee korte argument een (veel) langer argument maken. Als je alleen optellen, aftrekken, delen en vermenigvuldigen toestaat, is vermenigvuldigen de beste kandidaat daarvoor, maar die heeft nog de vervelende eigenschap dat het product van twee getallen nooit langer is dan de som van de lengtes van de operands.

Om een kortere som te krijgen zul je dus op z'n minst iets als machtsverheffen moeten toestaan, of een andere operatie waarvan het resultaat langer is dan de invoer.

Als je machtsverheffen toestaat, kun je x schrijven a^b + c, waarbij a = floor(x^1/b) en c = x - a^b. Waarschijnlijk kun je daarmee een heel eind komen; als c te lang wordt, kun je die op een vergelijkbare manier weer korter maken.

[ Voor 45% gewijzigd door Soultaker op 18-06-2011 17:05 ]

[Dido]

Inderdaad, machtsverheffen. Dat doe je al met jouw decimale notatie (tot 10⁹⁹ bij een getal van 100 cijfers decimaal).

Een optie is inderdaad hexadecimaal, maar er is geen enkele reden om daar te stoppen, en om je getal om te zetten naar base₃₂ of base₆₄.

Let wel dat je het steeds alleen maar hebt over een stukj epresentatie, want als je het getal als getal in een database opslaat schiet je er niet heel veel mee op.

Wat is precies het doel van deze exercitie, eigenlijk?

edit: een triviale benadering is natuurlijk om je getal base_n te noteren, als 10_n waarbij n=987654321234567890120987654323456765456787654678987654323456789234567654567654678909876543456789087

[ Voor 17% gewijzigd door Dido op 18-06-2011 17:06 ]

[Soultaker]

Dido schreef op zaterdag 18 juni 2011 @ 17:04:
Een optie is inderdaad hexadecimaal, maar er is geen enkele reden om daar te stoppen, en om je getal om te zetten naar base₃₂ of base₆₄.

Pff, z'n getal ís al één cijfer in basis 10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.

[Dido]

@ Soultaker: zie mijn edit. Dat het 1 getal is klopt, maar ik vermoed dat je cijfer bedoelt. En dan ben ik benieuwd naar dat ene cijfer van je

[Skit3000]

Alle standaard rekenkundige bewerkingen zijn toegestaan. Ook het bijhalen van Pi en andere in bijna alle programmeertalen bekende gedefinieerde talen zijn te gebruiken. Afhankelijk van hoe dit opgelost zou kunnen worden, kies ik een programmeertaal uit die alle nodige bewerkingen ondersteund.

Ik heb inderdaad ook met machtsverheffingen zitten stoeien. Daarmee kom je bij benadering wel in de buurt van het originele getal, maar afhankelijk van hoeveel cijfers je toe laat in de som, is ook alleen maar dat aantal cijfers van het antwoord van de som juist te voorspellen. Je moet dan met zoveel cijfers achter de komma gaan zitten rekenen dat je in de som al minimaal net zo veel cijfers hebt staan als in het oorsponkelijke getal om zeker te weten dat het antwoord juist is.

En een doel heb ik niet echt, ik breek alleen mijn hoofd hier al weken over en vroeg me af of ooit iemand anders al eens zoiets had geprobeerd

[RobIII]

Het kan voor sommige getallen en een heleboel niet Anders lees eens wat over Jan Sloot, dan besteed je je tijd nuttiger

[ Voor 33% gewijzigd door RobIII op 18-06-2011 17:20 ]

[benoni]

Knip het getal in stukjes van 9 tekens, schrijf die stukjes weg als een 30-bits integer?

[Dido]

Skit3000 schreef op zaterdag 18 juni 2011 @ 17:15:
Ik heb inderdaad ook met machtsverheffingen zitten stoeien. Daarmee kom je bij benadering wel in de buurt van het originele getal, maar afhankelijk van hoeveel cijfers je toe laat in de som, is ook alleen maar dat aantal cijfers van het antwoord van de som juist te voorspellen. Je moet dan met zoveel cijfers achter de komma gaan zitten rekenen dat je in de som al minimaal net zo veel cijfers hebt staan als in het oorsponkelijke getal om zeker te weten dat het antwoord juist is.

Onzin. Zet je decimale getal maar eens om naar hexadecimaal, dan raak je nul komma nul precisie kwijt, terwijl je minder cijfers hebt. Nu wordt het bij base₆₄ misschien wat lastig om karakers te vinden voor je cijfers, maar tot base₃₆ kun je gewoon volgens het stramien van je hexadecimale notatie doorwerken.

En een doel heb ik niet echt, ik breek alleen mijn hoofd hier al weken over en vroeg me af of ooit iemand anders al eens zoiets had geprobeerd

Tsja, wat probeer je nu eigenlijk? Zo kort mogelijk noteren? dan is 10 een triviale mogelijkheid, zelfs 1 zou kunnen, of Q. Of je er wat aan hebt is een tweede.

[Voutloos]

benoni schreef op zaterdag 18 juni 2011 @ 17:21:
Knip het getal in stukjes van 9 tekens, schrijf die stukjes weg als een 30-bits integer?

Opslagruimte wordt niet genoemd als reden. Als dat het punt is is het niet al te moelijk om efficienter op te slaan dan een varchar(100). En dan is een library met support voor grote nummers, opslaan als byte/blob datatype, of gebruik van compressie nog wat efficienter dan jouw trucje.

[ Voor 3% gewijzigd door Voutloos op 18-06-2011 17:32 ]

[RobIII]

Getallen en talstelsels FAQ: Representatie en opslag
Base X is wellicht een kortere notatie (=representatie) van een bepaald getal, maar qua opslag ga je er geen kont mee besparen; uiteindelijk is 't namelijk allemaal eenzelfde representatie van een bult bits. Efficiënter dan dat ga je 't ook niet kunnen opslaan voor iig een heleboel getallen. Dat er toevallig wat korte(re) manieren zijn om "6,494839840283956596617332956859e+1316" op te slaan (namelijk 567!) is leuk maar gaat nooit voor alle getallen op.

Maar dan ga ik wel uit dat we 't hebben over processors, bits, bytes, programmeertalen etc. Anders zie ik niet waarom dit topic in PRG staat en niet in W&L

[ Voor 11% gewijzigd door RobIII op 18-06-2011 17:32 ]

[Skit3000]

Het getal moet inderdaad een groepje data voorstellen. Normale compressietechnieken tellen meestal enkel hoe vaak bepaalde tekens voorkomen en gaan aan de hand daarvan deze tekens een kortere code geven. Ik dacht dat er misschien wel wat slimme rekenkundige trucjes waren waarmee je dat niet zou hoeven doen maar waarmee je wel (een klein beetje?) compressie kunt behalen.

[Matis]

We hebben dus te maken met een 333-bits getal;

log(10^100)/log(2) =
332.19...

Wat wil je eigenlijk bereiken? Minder bits als ruwe opslag? Een kortere (ascii) weergave?

@Edit; misschien toch maar eens kijken naar Huffman coding en/of Lempel-Ziv algorithm.

[ Voor 19% gewijzigd door Matis op 18-06-2011 17:39 ]

[Voutloos]

Skit3000 schreef op zaterdag 18 juni 2011 @ 17:36:
Het getal moet inderdaad een groepje data voorstellen. Normale compressietechnieken tellen meestal enkel hoe vaak bepaalde tekens voorkomen en gaan aan de hand daarvan deze tekens een kortere code geven.

...en doen hun output meestal binair, zodat je het efficienter opslaat. Nogmaals, lees de basics over representatie en zo. Even voorgekauwd: Als je enkel 10 mogelijke waardes in een byte opslaat, is dat niet efficient want een byte kan 256 verschillende waardes hebben.

Ik dacht dat er misschien wel wat slimme rekenkundige trucjes waren waarmee je dat niet zou hoeven doen maar waarmee je wel (een klein beetje?) compressie kunt behalen.

Die zijn er niet. Maar het is op zich best een leuk programmeersnackje voor een regenachtige dag om iets te schrijven dat een kortere wiskundige notatie zoekt. Maar dan gaan machtsverheffen en faculteiten je meer helpen dan enkel de operaties uit de topicstart.

[ Voor 13% gewijzigd door Voutloos op 18-06-2011 17:52 ]

[Xudonax]

Je kunt proberen om het getal te factoriseren. Ieder niet priemgetal is namelijk te factoriseren in twee of meer priemgetallen. Zie ook Wikipedia en http://www.ikhebeenvraag.be/vraag/10493. Het moeilijkste stuk gaat nu zijn hoe zo efficient mogelijk de priemgetallen vind waaruit het getal bestaat.

[Matis]

Als je de waardes van 0-9 als bit wilt gebruiken, heb je log(10)/log(2) (3.32) bits nodig. Als je dus twee decimale waardes in 7 bits stopt, heb je alsnog 350 bits nodig om je getal te representeren. Dat is dus weer dan de 333 bits die je in eerste instantie nodig had.
Op die manier van bits "clusteren" ga je de oorlog dus niet winnen. Tenzij je het getal als ascii op wilt slaan, dan kost het je 100 bytes, maar dat is natuurlijk zonde van je ruwe opslag.

[Skit3000]

Ok, dan houden we het nu even op iets onmogelijks maar wel leuk voor op regenachtige zaterdagmiddagen Enne, als het me lukt laat ik wel iets weten!

[Soultaker]

Dido schreef op zaterdag 18 juni 2011 @ 17:08:
@ Soultaker: zie mijn edit. Dat het 1 getal is klopt, maar ik vermoed dat je cijfer bedoelt. En dan ben ik benieuwd naar dat ene cijfer van je

Er staat al cijfer En dat cijfer is hetzelfde als jouw basis.

RobIII schreef op zaterdag 18 juni 2011 @ 17:16:
Het kan voor sommige getallen en een heleboel niet

Ik ging er hier vanuit dat je in som behalve cijfers nog extra karakters mag gebruiken (+, -, x, et cetera); dan heb je meer entropie per karakter en is het misschien wel mogelijk om alle getallen vanaf een bepaald beginpunt te verkleinen. Het staat of valt natuurlijk bij de vraag wat er precies is toegestaan in de som.

[Verwijderd]

je zou iets kunnen schrijven van

while willekeurig
{
- neem een willekeurig aantal tekens van het getal
- kijk of het te schrijven is als macht of breuk of product van willekeurige getallen
- als de gevonde factorizatie korter is dan het getal sla deze op en verminder getal met uitkomst factorizatie.
}
return de factorizaties

Dan moet je het "willekeurige" bruteforcen ((-> recursie (-> dynamisch programmeren))
Je zou het geheel nog willekeurig aantal keer kunnen loopen dat je dus de factorizaties weer gaat factorizeren.

getal = dan de som van de gevonde factorizaties
heb er erg in dat je programma ook nog een keer moet eindigen. Het is dus handig om je zoektocht naar factorizaties te optimalizeren en of te beperken tot wat je cpu aankan

[ Voor 32% gewijzigd door Verwijderd op 18-06-2011 18:13 ]

[Voutloos]

kruk, ik denk niet dat iemand iets aan die pseudo code heeft. Xudonax gaf al een link met concretere algoritmes.

[Verwijderd]

en ik denk
- na over de vraag van dit topic
- dat iemand door een wiel overnieuw uit te vinden niet dommer wordt
- dat mijn pseudocode niet faalt op een groot priemgetal
- jij wat vaker je mond moet houden als je niks te melden heb.
- dat ik dan nu wel een ban verdien door in te gaan op een flame.

[ Voor 11% gewijzigd door Verwijderd op 18-06-2011 18:26 ]

[Voutloos]

Excuses als ik het wat te direct zei, maar uiteindelijk komt het gewoon op bestaande algoritmes neer.

[H!GHGuY]

Mij is je vraag nog steeds niet duidelijk:
De informatie die je probeert om te zetten in een wiskundige expressie (geen som! a+b is een som), zijn dat die 100 tekens of is dat het getal zelf?

In het eerste geval, de 100 tekens, kun je met BCD (binary coded decimals) een heel eind of, zoals hierboven aangehaald, de base (die nu 10 is) verhogen naar 16 (hex) of hoger.

Als je over het getal zelf wil gaan dan kun je even kijken naar:
http://www.maths.surrey.a...onacci/fibmaths.html#alli
https://secure.wikimedia....i/Goldbach%27s_conjecture

[Dido]

Soultaker schreef op zaterdag 18 juni 2011 @ 18:02:
Er staat al cijfer En dat cijfer is hetzelfde als jouw basis.

Je hebt gelijk, er staat al cijfer.

Mijn basis bestaat echter uit 100 cijfers, dus dat jouw cijfer mijn basis is gaat er bij mij niet in

In jouw basis zou ik wel eens een notatie in 1 cijfer willen zien (in mijn basis gebruikte ik er twee!)

[Voutloos]

Jullie hebben allebei gelijk, wat Soultaker in zijn eerste post zegt klopt namelijk ook gewoon. Alleen kan hij de oplossing niet hier neerzetten aangezien we niet zoveel verschillende karakters hebben.

[Dido]

Voutloos schreef op zaterdag 18 juni 2011 @ 20:12:
Jullie hebben allebei gelijk, wat Soultaker in zijn eerste post zegt klopt namelijk ook gewoon. Alleen kan hij de oplossing niet hier neerzetten aangezien we niet zoveel verschillende karakters hebben.

Kies maar een teken, neem Q. Laat me maar zien hoe dat teken Q in de door Soultaker genoemde base gelijk is aan het getal van de TS.

Neem je het getal van de TS als basis, dan heb je normaliter alsnog 2 (twee!) cijfers nodig. Namelijk de 1 en de 0.

[Soultaker]

In een genormaliseerd talstelsel met basis B kunnen alle (niet-negatieve) getallen <B door één cijfer worden gerepresenteerd.

Laten we het getal uit de TS N noemen. In elk talstel B > N wordt N gerepresenteerd met één enkel cijfer; N. Ik nam 10¹⁰⁰ omdat het getal in de TS toevallig honderd cijfers had, maar ik had net zo goed B=N+1 kunnen kiezen. Het klopt dat als je B≤N kiest, dat je dan méér dan een cijfer nodig hebt. (In z'n algemeenheid heb je floor(log(N)/log(B))+1 cijfers nodig om een positief getal N in basis B uit te drukken.)

[ Voor 25% gewijzigd door Soultaker op 18-06-2011 21:15 ]

[Dido]

* Dido gaat koffie drinken, want hij zit al een paar uur wat over het hoofd te zien

Ik heb dan ook nog vakantie, geldt dat als excuus?