Toon posts:

Getal berekenen ipv voluit noteren

Pagina: 1
Acties:

  • Skit3000
  • Registratie: Mei 2005
  • Laatst online: 08-06 23:22
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
  • Registratie: Augustus 2007
  • Laatst online: 09-06 22:21
Omzetten naar hexadecimaal?

Alcohol, the cause and solution to all of life's problems


  • Soultaker
  • Registratie: September 2000
  • Laatst online: 08-06 20:53
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 ab + c, waarbij a = floor(x1/b) en c = x - ab. 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
  • Registratie: Maart 2002
  • Laatst online: 09:45

Dido

heforshe

Inderdaad, machtsverheffen. Dat doe je al met jouw decimale notatie (tot 1099 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 base32 of base64.

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 basen te noteren, als 10n waarbij n=987654321234567890120987654323456765456787654678987654323456789234567654567654678909876543456789087

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

Wat betekent mijn avatar?


  • Soultaker
  • Registratie: September 2000
  • Laatst online: 08-06 20:53
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 base32 of base64.
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
  • Registratie: Maart 2002
  • Laatst online: 09:45

Dido

heforshe

@ 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 ;)

Wat betekent mijn avatar?


  • Skit3000
  • Registratie: Mei 2005
  • Laatst online: 08-06 23:22
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
  • Registratie: December 2001
  • Laatst online: 03:20

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

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

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

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Roses are red Violets are blue, Unexpected ‘{‘ on line 32.

Over mij


  • benoni
  • Registratie: November 2003
  • Niet online
Knip het getal in stukjes van 9 tekens, schrijf die stukjes weg als een 30-bits integer?

  • Dido
  • Registratie: Maart 2002
  • Laatst online: 09:45

Dido

heforshe

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 base64 misschien wat lastig om karakers te vinden voor je cijfers, maar tot base36 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.

Wat betekent mijn avatar?


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
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]

{signature}


  • RobIII
  • Registratie: December 2001
  • Laatst online: 03:20

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

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]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Roses are red Violets are blue, Unexpected ‘{‘ on line 32.

Over mij


  • Skit3000
  • Registratie: Mei 2005
  • Laatst online: 08-06 23:22
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
  • Registratie: Januari 2007
  • Laatst online: 09:39

Matis

Rubber Rocket

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]

If money talks then I'm a mime
If time is money then I'm out of time


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
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]

{signature}


  • Xudonax
  • Registratie: November 2010
  • Laatst online: 08-06 08:42
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
  • Registratie: Januari 2007
  • Laatst online: 09:39

Matis

Rubber Rocket

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.

If money talks then I'm a mime
If time is money then I'm out of time


  • Skit3000
  • Registratie: Mei 2005
  • Laatst online: 08-06 23:22
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
  • Registratie: September 2000
  • Laatst online: 08-06 20:53
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.

Anoniem: 392524

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 Anoniem: 392524 op 18-06-2011 18:13]


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
kruk, ik denk niet dat iemand iets aan die pseudo code heeft. Xudonax gaf al een link met concretere algoritmes. :)

{signature}


Anoniem: 392524

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 Anoniem: 392524 op 18-06-2011 18:26]


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
Excuses als ik het wat te direct zei, maar uiteindelijk komt het gewoon op bestaande algoritmes neer.

{signature}


  • H!GHGuY
  • Registratie: December 2002
  • Niet online

H!GHGuY

Try and take over the world...

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

ASSUME makes an ASS out of U and ME


  • Dido
  • Registratie: Maart 2002
  • Laatst online: 09:45

Dido

heforshe

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!)

Wat betekent mijn avatar?


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
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. :Y)

{signature}


  • Dido
  • Registratie: Maart 2002
  • Laatst online: 09:45

Dido

heforshe

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. :Y)
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.

Wat betekent mijn avatar?


  • Soultaker
  • Registratie: September 2000
  • Laatst online: 08-06 20:53
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 10100 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
  • Registratie: Maart 2002
  • Laatst online: 09:45

Dido

heforshe

* 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? :+

Wat betekent mijn avatar?

Pagina: 1


Tweakers maakt gebruik van cookies

Tweakers plaatst functionele en analytische cookies voor het functioneren van de website en het verbeteren van de website-ervaring. Deze cookies zijn noodzakelijk. Om op Tweakers relevantere advertenties te tonen en om ingesloten content van derden te tonen (bijvoorbeeld video's), vragen we je toestemming. Via ingesloten content kunnen derde partijen diensten leveren en verbeteren, bezoekersstatistieken bijhouden, gepersonaliseerde content tonen, gerichte advertenties tonen en gebruikersprofielen opbouwen. Hiervoor worden apparaatgegevens, IP-adres, geolocatie en surfgedrag vastgelegd.

Meer informatie vind je in ons cookiebeleid.

Sluiten

Toestemming beheren

Hieronder kun je per doeleinde of partij toestemming geven of intrekken. Meer informatie vind je in ons cookiebeleid.

Functioneel en analytisch

Deze cookies zijn noodzakelijk voor het functioneren van de website en het verbeteren van de website-ervaring. Klik op het informatie-icoon voor meer informatie. Meer details

janee

    Relevantere advertenties

    Dit beperkt het aantal keer dat dezelfde advertentie getoond wordt (frequency capping) en maakt het mogelijk om binnen Tweakers contextuele advertenties te tonen op basis van pagina's die je hebt bezocht. Meer details

    Tweakers genereert een willekeurige unieke code als identifier. Deze data wordt niet gedeeld met adverteerders of andere derde partijen en je kunt niet buiten Tweakers gevolgd worden. Indien je bent ingelogd, wordt deze identifier gekoppeld aan je account. Indien je niet bent ingelogd, wordt deze identifier gekoppeld aan je sessie die maximaal 4 maanden actief blijft. Je kunt deze toestemming te allen tijde intrekken.

    Ingesloten content van derden

    Deze cookies kunnen door derde partijen geplaatst worden via ingesloten content. Klik op het informatie-icoon voor meer informatie over de verwerkingsdoeleinden. Meer details

    janee