mathe->informatik algorithmus

dettus

dettus

Bicycle User
hallo freunde der knackigen raetsel!

ich habe hier mal eben folgendes problem:
gegeben seien zwei ganzzahlige werte A und B. beide maximal 64 bit gross.
nun nimmt man den einheitskreis und unterteilt ihn im uhrzeigersinn in B gleich grosse teilstuecke.
von diesen suche ich jetzt die X/Y-koordinaten wo der A-te abschnitt beginnt.
das kann man eigentlich ganz einfach nachrechnen:
Code: 
X=\cos\left(-2\pi\frac{A}{B}\right)   %% X=cos(-2pi(A/B))
Y=\sin\left(-2\pi\frac{A}{B}\right)   %% Y=sin(-2pi(A/B))
zum beispiel hat man fuer A=1, B=8 ein 45grad-winkel nach unten, A=7, B=8 ein 45grad-winkel nach oben.

mein gefuehl sagt mir jetzt aber dass man das auch ohne den umweg ueber den bruch und sinus und cosinus ausrechnen kann. vielleicht mit intervallschachtelung oder sowas.
jemand eine idee?
 
A=0 liegt also auf der X-Achse? Und der Radius ist 1?

Ohne sin und cos wirst du das wahrscheinlich nicht ohne Weiteres hinbekommen.. Den Bruch halte ich auch für unumgänglich, da du die einzelnen Winkel ja 2pi/B groß hast und du den A-ten davon willst (also mit A multiplizieren).

Willst du den Algorithmus für ein spezielles System optimieren? Evtl. eins ohne FPU?
 
Du kannst die Sinus und Kosinusfunktionen mit irgendeinem Algorithmus approximieren. Dann bekommst du eine ganz normales Polynom raus.
 
Kamikaze schrieb:
Du kannst die Sinus und Kosinusfunktionen mit irgendeinem Algorithmus approximieren. Dann bekommst du eine ganz normales Polynom raus.
Zum Vergrößern anklicken....

Du meinst wohl das hier, oder?
Code: 
sin z = \frac{e^{iz}-e^{-iz}}{2i}=z-\frac{z^3}{3!}+\frac{z^5}{5!}-...
cos z = \frac{e^{iz}+e^{-iz}}{2}=1-\frac{z^2}{2!}+\frac{z^4}{4!}-...


Eine Möglichkeit wäre doch auch die Verwendung von Polarkoordinaten, oder? OK, da brauchst du dann den Winkel, aber der ist ja durch die Unterteilung in B gleiche Stücke quasi gegeben. Den Sinus und Kosinus sparst Du dir dabei zwar nicht, aber den Bruch...


Vielleicht hilft's ja was
 
Wenn A und B nicht beliebig wählbar sind, kann man sich die Ergebnisse auch vorberechnen lassen. Was sind schon paar MB an Daten in der heutigen Zeit?
 
@oneone: richtig. ich bin chipdesigner. saugeiler job! fuer jedes problem das du hast schreibst du kein proggie. sondern definierst dir deinen ganz eingenen prozessor selbst. und weil ich fuer mein derzeitiges projekt keine lust habe mir eine fpu zu bauen (oder eine fertige zu nehmen, wo bleibt denn da der spass... ;) ) muss es auch ohne gehen.

@kamikaze,daemon: ihr redet von potenzreihen. die will ich moeglichst auch vermeiden. weil, in deinem beispiel ist z=-2pi(A/B). da hab ich ploetzlich zwei brueche drinne. wie gesagt: am liebsten waere mir da sowas wie eine intervallschachtelung.

@nakal: lol. danke. aber leider sind A und B jeweils 64-bit zahlen.
 
Moinsen,

anbei ein Vorschlag eines Kollegen von mir. Ich bin dafür zu dämlich.

(1) Beachte aber, welchen Abschnitt Du meinst ! Der erste Abschnitt mit A=1 im Uhrzeigersinn beginnt bei der X-Achse ! Also ist der Winkel = 0°. Dann beginnt der 7.Abschnitt mit A=7 bei 270° im Uhrzeigersinn. Das entspricht 90° nach oben.
(2) Andere Möglichkeit: Man nummeriert die Abschnitte von 0 bis 7. Dann beginnt der 0-te Abschnitt bei der X-Achse mit Winkel 0°. Der 1.Abschnitt würde dann einem Winkel von 45° nach unten entsprechen. Der 7.Abschnitt entspricht dann einem Winkel von 315°, also 45 ° nach oben.
(3) Die Formel ist korrekt für die 2.Möglichkeit.
(4) Im allgemeinen muss man die Formeln mit Sinus und Cosinus verwenden. Für die betrachteten Spezialfälle ist die Berechnung aber einfacher:
a. A=0 und B=8. Dann ist der Winkel =0°. Es gilt X=1 und Y=0.
b. A=1 und B=8. Dann ist der Winkel=45°. Da die X- und die Y-Achse senkrecht aufeinander stehen, folgt nach dem Satz des Pythagoras X^2 + Y^2 = 1.
Da Y = -X , gilt 2 * X^2 = 1, also X = sqrt(1/2) = -0,7071 nach Überlegung des Vorzeichens. Y = sqrt(1/2) = 0,7071
c. A=3 und B=8. Winkel=135°. Analog zu b folgt X = -0,7071 und Y = -07071 nach Vorzeichenbetrachtung.
d. A=5 und B=8. Winkel=225°. Analog zu b folgt X=-0,7071 und Y=0,7071 nach Vorzeichenbetrachtung.
e. A=7 und B=8. Winkel=315° also 45° nach oben. Analog zu b folgt X = 0,7071 und Y= 0,7071 nach Vorzeichenbetrachtung.
f. Die Vorzeichenbetrachtung ist nötig, da die Gleichung nach dem Satz des Pythagoras 4 Lösungen in der Ebene hat.

Beste Grüße
kraekers
 
Wer sagt denn, dass es um ein Display gehen muss? Wenn der Chip in eine Bearbeitungsmaschine käme, würde ich mich für eine geringere Genauigkeit schön bedanken (Fertigungstoleranzen im µ-Bereich sind bei einigen Prozessschritten durchaus erforderlich...)
 
Moin,

leider ist meinem Kollegen ein kleiner Fehler unterlaufen, hier die Korrektur:

Vorzeichenfehler bei Fall (4) b :

Es muss im Fall A=1 und B=8, Winkel= 45° als Lösung heißen X=sqrt(1/2)=0,7071 und Y=-sqrt(1/2)=-07071 !



Beste Grüße
kraekers
 
das ganz ist natuerlich nicht fuer ein display.
das mit den x/y-koordinaten ist nur zur veranschaulichung.
leider darf ich euch nicht erzaehlen was fuer ein spezielles problem das ist.

64-bit zahlen sind auf jeden fall durchaus realistisch!
 
Hallo dettus,

schau dir doch mal die Algorithmen von
(*) Bresenham (Intervallschachtelung)
(*) Maxwell-Baker (Intervallschachtelung)
(*) Horn
an.

Wenn ich mich an mein Studium recht entsinne, lassen sich diese Algorithmen sehr leicht mit RISC-Kommandos realisieren.

Viel Spaß dabei

JueDan
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben