🚀 go-pugleaf

In <1992Apr11.181119.10665@wega.rz.uni-ulm.de> ORAKEL@rzmain.rz.uni-ulm.de writes:

> Ich suche einen Algorithmus (kein fertiges (C-)Programm!) oder
> einen entsprechenden Literaturhinweis fuer folgendes Problem:
> 
> Aus einer realen Zahl x moechte ich einen Bruch der Form:
>         
>      a*sqrt(b)
>     -----------	    ( sqrt = Quadratwurzel )
>      c*sqrt(d)
> 
> bilden, wobei er moeglichst einfach (gekuerzt) sein sollte.

Ich vergass zu erwaehnen, dass a,b,c und d ganze Zahlen sein sollen und
dass mir 12 Dezimalstellen Genauigkeit ausreichen. Ich brauche nicht
unbedingt ein mathematisch exaktes Ergebnis.
Also:

  |        a*sqrt(b)   |        -12
  |  x -  -----------  |  <  10
  |        c*sqrt(d)   |


/---Ulli Horlacher---Rechenzentrum Uni Ulm---Oberer Eselsberg---7900 Ulm---\
\   orakel@dulruu51.bitnet |  orakel@rz.uni-ulm.de |  framstag@uni-ulm.de  /
 \------------------------------------------------------------------------/
 | "C muss wohl eine Art von Onanie fuer Haecker sein" Sabine Stehmer, HP |
---------------------------------------------------------------------------
COPYRIGHT:  DIESER ARTIKEL IST COPYRIGHT BY ULLI HORLACHER UND DARF
            AUSSERHALB DES USENETS OHNE SCHRIFTLICHE GENEHMIGUNG DES AUTORS
            (IN DIESEM FALL IST DER KOMPLETTE NEWSHEADER MIT ANZUGEBEN)
            WEDER NACHGEDRUCKT NOCH ZITIERT NOCH SONSTIRGENDWIE REFERIERT
            WERDEN, AUCH NICHT AUSZUGSWEISE. ZUWIDERHANDLUNGEN WERDEN
            STRAFRECHTLICH VERFOLGT.

ORAKEL@rzmain.rz.uni-ulm.de (Framstag) writes:

>In <1992Apr11.181119.10665@wega.rz.uni-ulm.de> ORAKEL@rzmain.rz.uni-ulm.de writes:

>> Ich suche einen Algorithmus (kein fertiges (C-)Programm!) oder
>> einen entsprechenden Literaturhinweis fuer folgendes Problem:
>> 
>> Aus einer realen Zahl x moechte ich einen Bruch der Form:
>>         
>>      a*sqrt(b)
>>     -----------	    ( sqrt = Quadratwurzel )
>>      c*sqrt(d)
>> 
>> bilden, wobei er moeglichst einfach (gekuerzt) sein sollte.

>Ich vergass zu erwaehnen, dass a,b,c und d ganze Zahlen sein sollen und
>dass mir 12 Dezimalstellen Genauigkeit ausreichen. Ich brauche nicht
>unbedingt ein mathematisch exaktes Ergebnis.
>Also:

>  |        a*sqrt(b)   |        -12
>  |  x -  -----------  |  <  10
>  |        c*sqrt(d)   |

Trivialloesung:
b = d = 1
c = 10 ^ 12
a = x * 10 ^ 12
Kuerzen von a und c durch ggt(a, c).

Ich glaube Dein Problem ist nicht ganz klar geworden.  Beschreibe
es doch mal genauer.

Holger
---
Name  : Holger Joist
E-Mail: hrjoist@medusa.informatik.uni-erlangen.de
--
I am a signature antibody. Copy me into your signature and
your signature is immune from all known signature viruses.

In <1992Apr13.112025.3142@informatik.uni-erlangen.de> hrjoist@immd4.informatik.uni-erlangen.de writes:

> Trivialloesung:
> (...)
> 
> Ich glaube Dein Problem ist nicht ganz klar geworden.  Beschreibe
> es doch mal genauer.

Keiner versteht mich, buhuhu ;-)
Ich hatte es befuerchtet, dass meine mathematische Formulierungen zu
wuenschen lassen... also nochmal, mit etwas mehr Worten:

Die Trivialloesung ist mir bekannt, allerdings hatte ich geschrieben:

> (...), wobei (der Bruch) moeglichst einfach (gekuerzt) sein sollte.

Mit moeglichst einfach, meinte ich (voellig unmathematisch und unpraezise),
dass der Bruch Quadratwurzeln enthalten sollte, wenn moeglich. Hmm auch
nicht besser formuliert.
Ich versuchs mal mit nem Beispiel:

   sin(pi/4) = 0.7071067812 = 1/sqrt(2) = 33461/47321  (bei 12 Stellen) 

1/sqrt(2) ist "anschaulicher" als 33461/47321
Mit so einem Ergebnis laesst sich oft eine bessere Aussage (zb in der
Kurvendiskussion) machen, als mit einem Ganzzahlenbruch.

Es ist mir schon klar, dass sich nicht fuer jede rationale (ich schrieb
im ersten Posting zuerst "real", das war ein typo) Zahl sich so ein
"schoener" Wurzelbruch finden laesst.
Ein Programm, das es macht ist zb Maple.

Jetzt moechte ich gerne wissen, wie das geht :-)


/---Ulli Horlacher---Rechenzentrum Uni Ulm---Oberer Eselsberg---7900 Ulm---\
\   orakel@dulruu51.bitnet |  orakel@rz.uni-ulm.de |  framstag@uni-ulm.de  /
 \------------------------------------------------------------------------/
 | "C muss wohl eine Art von Onanie fuer Haecker sein" Sabine Stehmer, HP |
---------------------------------------------------------------------------
COPYRIGHT: Fuer Veroeffentlichungen _AUSSERHALB_ des Newssystemes gelten 
           _MEINE_ Geschaeftsbedingungen. Nichtbeachtung wird in der Regel
           zivil- und strafrechtliche Folgen nach sich ziehen.       

ORAKEL@rzmain.rz.uni-ulm.de (Framstag) writes:

[Diskussion "uber ein Problem gel"oschst]

>Ein Programm, das es macht ist zb Maple.

Falsch. Maple konvertiert nicht irgendwelche Fliesskommazahlen in
das wahrscheinlich richtige Ergebnis, Maple rechnet *symbolisch*.
F"ur Maple ist sqrt(2) diejenige positive reelle Zahl, deren
Quadrat zwei ist, und das hat f"ur Maple mit 1.41421556237.. nix zu tun.

Maple kennt auch die Werte der trigonometrischen Funktionen
an manchen der Stellen, an denen sie algebraisch sind.
Da ist ganz einfach eine Abfrage eingebaut. Eigentlich ist es noch
einfacher: Das remember table f"ur den sin() ist schon vorgeladen.
Probier doch mal op(4,op(sin)).

>Jetzt moechte ich gerne wissen, wie das geht :-)

Wie was geht ? Computer Algebra ist ein weites Feld...
Und wie Maple das mit dem Sinus und der sqrt(3) macht, habe ich Dir
gerade erkl"art.

---
------------------------------------------------------------------------------
    Klaus Kalb     | mail :  IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany 
 Werch ein Illtum  | email:  kskalb@immd1.informatik.uni-erlangen.de   
------------------------------------------------------------------------------

From article <1992Apr11.181119.10665@wega.rz.uni-ulm.de>, by ORAKEL@rzmain.rz.uni-ulm.de (Framstag):
> Ich suche einen Algorithmus (kein fertiges (C-)Programm!) oder
> einen entsprechenden Literaturhinweis fuer folgendes Problem:
> 
> Aus einer realen Zahl x moechte ich einen Bruch der Form:
>         
>      a*sqrt(b)
>     -----------	    ( sqrt = Quadratwurzel )
>      c*sqrt(d)
> 
> bilden, wobei er moeglichst einfach (gekuerzt) sein sollte.
> Sinn ist es, am Ende einer Rechnung eine Zahl darzustellen, die einem etwas
> "sagt".  3/sqrt(2)  ist halt anschaulicher als  2.121320344
> 
> Die Ausgabe ist mir dabei nicht wichtig, ich brauche nur die Variablen
> a,b,c,d.
> 
> Ich hab schon fertige Programme gesehen, die so was machen, leider alle in
> Form von Compilaten. Nix fuer reverse engeneering.

Kochrezept: 

    (X * 10E12)^2
    -------------
    (10E12)^2

    Primfaktorzerlegung von Zaehler und Nenner bestimmen, kuerzen,
    paarweise Faktoren bilden a und c, die restlichen b und d. Evtl.
    nach dem kuerzen noch mit gemeinsamen Faktoren in Zaehler und
    Nenner ergaenzen, um moeglichst gleichgrosse a,b,c und d zu
    bekommen, wenn dies erwuenscht wird.
     
---

             Toerless.Eckert@informatik.uni-erlangen.de
    /C=de/A=dbp/P=uni-erlangen/OU=informatik/S=Eckert/G=Toerless/
             35 hour week ? i've got a 35 hour day

eckert@immd4.informatik.uni-erlangen.de (Toerless Eckert) writes:
>From article <1992Apr11.181119.10665@wega.rz.uni-ulm.de>, by ORAKEL@rzmain.rz.uni-ulm.de (Framstag):
>> 
>> Aus einer realen Zahl x moechte ich einen Bruch der Form:
>>         
>>      a*sqrt(b)
>>     -----------	    ( sqrt = Quadratwurzel )
>>      c*sqrt(d)
>> 
>> bilden, wobei er moeglichst einfach (gekuerzt) sein sollte.

Wenn das man ueberhaupt eindeutig geht. Wie andere ja schon gesagt haben,
scheint Deine Beobachtung, dass andere Programme das schon koennen, nicht
gut belegbar zu sein. Wir haben immerhin nur einen Eingangswert, Du
willst aber 4 (VIER) Ausgangswerte raushaben, uff.

Also lass mal sehen...

Ich hab das eben mal in AmigaBasic (:-) aus dem Aermel geschuettelt.
Es gibt bestimmt noch elegantere Methoden als diese Brute-Force-Schleifen.

INPUT x
z%=1:n=1
IF x>1 THEN z%=x
z%=z%-1
r=x
WHILE INKEY$=""
  z%=z%+1
  PRINT :PRINT z%
  n%=z%/x:zs%=SQR(z%)
  FOR i%=1 TO zs%
    zs=SQR(i%):z1%=z%/zs
    z=z1%*zs
    PRINT z%;":";z1%;"* SQR(";i%;")"
    ns%=SQR(n%)
    FOR j%=1 TO ns%
      ns=SQR(j%):n1%=z/(ns*x)
      y=z/(n1%*ns)
      r1=ABS((y-x)/x)
      IF r1<r THEN
        ' ggt von z1% und n1% suchen
        z2%=z1%:n2%=n1%:m%=2
        WHILE m%<=z2% AND m%<=n2%
          IF INT(z2%/m%)=z2%/m% AND INT(n2%/m%)=n2%/m% THEN
            z2%=z2%/m%:n2%=n2%/m%
            r1=ABS((z2%*zs/(n2%*ns)-x)/x)
              ELSE
            m%=m%+1
            END IF
          WEND
        PRINT 
        PRINT z2%;"* SQR(";i%;")"
        PRINT n2%;"* SQR(";j%;")";r1
        r=r1
        END IF
      NEXT
    NEXT
  WEND

Bemerkung: In Basic darfst Du die *verschiedenen* Variablen n (real)
und n% (Integer) nebeneinander benutzen, in C musst Du die Namen echt
verschieden machen.

Viel Spass!

-- 
Best regards, Dr. Peter Kittel  // E-Mail to  \\  Only my personal opinions... 
Commodore Frankfurt, Germany  \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
                                   or  peterk@public.sub.org

In <1992Apr14.080848.14242@public.sub.org> peterk@public.sub.org writes:

> Wenn das man ueberhaupt eindeutig geht. Wie andere ja schon gesagt haben,
> scheint Deine Beobachtung, dass andere Programme das schon koennen, nicht
> gut belegbar zu sein. Wir haben immerhin nur einen Eingangswert, Du
> willst aber 4 (VIER) Ausgangswerte raushaben, uff.

Hab ich nach einer eindeutigen Loesung verlang? :-)
Ich schrieb was von "moeglichst einfach usw"...
Ich habe inzwischen schon einige Antworten bekommen, auch via mail, ich
werde mal schauen, welche fuer mich die beste ist, denn
> Es gibt bestimmt noch elegantere Methoden als diese Brute-Force-Schleifen.

kommt fuer mein Problem nicht in Frage. Das ganze soll auf einem
Taschenrechner laufen und da ist u.a. die Rechenzeit eine kritische
Groesse.


/---Ulli Horlacher---Rechenzentrum Uni Ulm---Oberer Eselsberg---7900 Ulm---\
\   orakel@dulruu51.bitnet |  orakel@rz.uni-ulm.de |  framstag@uni-ulm.de  /
 \------------------------------------------------------------------------/
 | "C muss wohl eine Art von Onanie fuer Haecker sein" Sabine Stehmer, HP |
---------------------------------------------------------------------------
COPYRIGHT: Fuer Veroeffentlichungen _AUSSERHALB_ des Newssystemes gelten 
           _MEINE_ Geschaeftsbedingungen. Nichtbeachtung wird in der Regel
           zivil- und strafrechtliche Folgen nach sich ziehen.       

Es gibt ein sehr gutes Verfahren um reele Zahlen in Brueche zu verwandeln.
Damit das was nuetzt, quadriere erst einmal die Gleichung

		(a*sqrt(b))/(c*sqrt(d))=r =>

		a*a*b/(c*c*d)=r*r

Finde also erst einmal einen Bruch fuer r*r und fiesele dann mit Primfaktorzerlegung
a, b, c und d daraus heraus.

Das Verfahren um aus einer reellen Zahl s einen Bruch zu machen sieht so aus:

Zerlege s in Integerzahl und Mantisse: s=i0+s0 (i0 ganzzahlig, s0 zwischen 0 und 1)
Zerlege 1/s0 in Integer und Mantisse: 1/s0=i1+s1,
zerlege 1/s1 in Integer und Mantisse: 1/s1=i2+s2 usw. Hoere irgendwann auf damit :)

Dann gilt s=io+1/(i1+1/(i2+1/(i3+....))))....

Das ist dann nur noch auf einen Hauptnenner zu bringen. Das Verfahren
konvergiert sehr schnell auf eine gute Approximation fuer s. Im Falle dass s
eine rationale Zahl ist, wird irgendein sn gleich null. Dann kann man sowieso
aufhoeren.

Viel Spass,

Udo Lenz, Email lenz@bl.physik.uni-muenchen.de