Le coordinate dei punti costruttivi possono essere rappresentate esattamente?

Question

Mi piacerebbe scrivere un programma che consenta agli utenti di disegnare punti, linee e cerchi come se fossero una scala e una bussola. Allora voglio essere in grado di rispondere alla domanda "sono questi tre punti collineari?" Per rispondere correttamente, ho bisogno di evitare errori di arrotondamento durante il calcolo dei punti.

È possibile? Come posso rappresentare i punti in memoria?

(ho guardato in alcune librerie numerici inusuali, ma non ho trovato niente che sosteneva di offrire sia aritmetica esatta e confronti esatte che sono garantiti per terminare.)

Answer 1

Sì.

Consiglio vivamente Introduction to constructions, che è una buona guida di base.

Fondamentalmente è necessario essere in grado di calcolare con constructible numbers - i numeri che sono o razionali, o della forma a + b sqrt (c) dove a, b, c sono stati creati in precedenza (vedi pagina 6 su quel PDF). Ciò potrebbe essere fatto con il tipo di dati algebrici (ad esempio data C = Rational Integer Integer | Root C C C in Haskell, dove Root a b c = a + b sqrt (c)). Tuttavia, non so come eseguire test con quella rappresentazione.

Due approcci possibili sono:

• numeri costruibili sono un sottoinsieme di algebraic numbers, in modo da poter utilizzare i numeri algebrici. Tutti i numeri algebrici possono essere rappresentati utilizzando i polinomi di cui sono radici. Le operazioni sono computabili, quindi se rappresenti un numero a con polinomio p eb con polinomiale q (p (a) = q (b) = 0), allora è possibile trovare un polinomio r tale che r (a + b) = 0. Questo avviene in alcuni CAS come Mathematica, example. Vedi anche: Computional algebraic number theory - chapter 4

• Utilizzare il test di Tarski e rappresentare i numeri. È lento (doppiamente esponenziale o così), ma funziona :) Esempio: per rappresentare sqrt (2), utilizzare la formula x^2 - 2 & & x> 0. È possibile scrivere equazioni per le linee lì, controllare se i punti sono vicini ecc Vedere A suite of logic programs, including Tarski's test

Se si gira a computable numbers, poi l'uguaglianza, ecc colinearity ottenere indecidibile.

Answer 2

Se gli assi della griglia sono interi valutati poi il la risposta è abbastanza semplice, i punti sono esattamente colineari o non lo sono.

In genere, tuttavia, uno funziona con numeri reali (bene, punti mobili) e quindi disegna i valori arrotondati sullo schermo che esistono nello spazio intero. In questo caso non hai altra scelta che scegliere una tolleranza e usarla per determinare la colinearità. Tienilo piccolo e gli utenti non sapranno mai la differenza.

Answer 3

Credo che l'unico modo in cui questo sarebbe possibile se si è utilizzato una rappresentazione simbolica, al contrario di cercare di rappresentare coordinare direttamente i valori - in modo che avrebbe per evitare di cercare di costringere valori come sqrt (2) in qualche formato numerico. Il numero si occuperà di numeri irrazionali che non sono rappresentabili finitamente in binario, decimale, o qualsiasi altra notazione posizionale.

Answer 4

Non consiglio di provare a renderlo perfettamente esatto.

Il primo motivo è quello che stai chiedendo qui, l'errore di arrotondamento e tutto ciò che viene fornito con i calcoli in virgola mobile.

Il secondo è che è necessario arrotondare l'input mentre il mouse e lo schermo funzionano con numeri interi. Quindi, inizialmente tutti gli input dell'utente sarebbero interi, e il tuo output sarebbe un numero intero.

Inoltre, dal punto di vista dell'usabilità, è più semplice fare clic in un punto (ad esempio in una riga) e l'interfaccia considera che si sta facendo clic nel punto stesso.

Answer 5

Per espandere sulla risposta Jim Lewis s' un po', se si vuole operare su punti che sono costruibili dagli interi con aritmetica esatta, dovrai essere in grado di operare sulle rappresentazioni della forma:

a + b sqrt(c) 

dove a, b e c sono numeri razionali o rappresentazioni nella forma sopra riportata. Wikipedia ha un articolo abbastanza decente sul tema di quali punti sono costruibili.

Rispondere alla domanda di uguaglianza esatta (necessaria per stabilire la colinearità) con tali rappresentazioni è un problema piuttosto complicato.

Answer 6

Se si tenta di confrontare le coordinate per i punti, si ha un problema. Lasciando da parte la co-linearità per un momento, che ne dici di capire se due punti sono uguali o no?

Supponendo che uno abbia assegnato delle coordinate e l'altro sia una costruzione di una bussola a partire da certe altre coordinate, si vuole determinare con certezza se sono lo stesso punto o meno.In entrambi i casi è un teorema della geometria euclidea, non è qualcosa che puoi misurare. Puoi dimostrare che non sono gli stessi individuando alcune differenze nelle loro coordinate (ad esempio calcolando i decimali di ciascuno finché non incontrerai una differenza). Ma in generale per dimostrare che sono gli stessi non può essere fatto con metodi approssimativi. Calcola il numero di posizioni decimali che desideri di alcune espansioni di 1/sqrt(2) e sqrt(2)/2, e puoi dimostrare che sono molto vicine tra loro, ma non proverai mai di essere uguali. Ciò richiede algebra (o geometria).

Analogamente, per dimostrare che i tre punti sono co-lineari è necessario un software di dimostrazione del teorema. Rappresentano i punti A, B, C con le loro costruzioni e tentano di dimostrare il teorema "A, B e C sono colineari". Questo è molto difficile - il tuo programma dimostrerà alcuni teoremi ma non altri. Molto più facile è chiedere all'utente di provare che sono co-lineari, e quindi verificare (o smentire) quella prova, ma probabilmente non è quello che vuoi.

Answer 7

Sembra che tu stia chiedendo, in effetti, "la normale matematica (intero o virgola mobile) utilizzata dai computer può essere fatta per rappresentare perfettamente i numeri reali, senza errori di arrotondamento?" E, naturalmente, la risposta è "No." Se vuoi la correttezza teorica, allora sarai bloccato con il problema molto più difficile della manipolazione simbolica e codificando l'equivalente delle inferenze che si fanno nella geometria. (In breve, sono d'accordo con Steve Jessop, sopra.)

Answer 8

In generale, i punti costruibili possono avere una forma simbolica arbitrariamente complessa, quindi è necessario utilizzare una rappresentazione simbolica per lavorarli esattamente. Come notato in precedenza da Stephen Canon, spesso avete bisogno dei numeri della forma a + b * sqrt (c), dove a e b sono razionali e c è un numero intero. Tutti i numeri di questo modulo formano un insieme chiuso sotto operazioni aritmetiche. Ho scritto some C++ classes (vedi rational_radical1.h) per lavorare con questi numeri se è tutto ciò che serve.

E 'anche possibile costruire numeri che sono somme di un numero qualsiasi di termini di multipli razionali di radicali. Quando si ha a che fare con più di un radicando, i numeri non vengono più chiusi in moltiplicazione e divisione, quindi sarà necessario memorizzarli come array di coefficienti razionali a lunghezza variabile. La complessità temporale delle operazioni sarà quindi quadratica nel numero di termini.

Per andare ancora oltre, è possibile costruire la radice quadrata di un dato numero, in modo da poter potenzialmente avere radici quadrate nidificate. Qui, le rappresentazioni devono essere strutture ad albero per gestire la gerarchia delle radici. Sebbene sia difficile da attuare, in linea di principio non vi è nulla che vi impedisca di lavorare con queste rappresentazioni. Non sono sicuro di quali siano i numeri aggiuntivi che possono essere costruiti, ma oltre un certo punto, la tua rappresentazione simbolica sarà sufficientemente espressiva per gestire classi di numeri molto grandi.

Addendum

Abbiamo trovato questo Google Books link.

Answer 9

Alcuni pensieri nella speranza che possano aiutare.

Il tipo di costruzioni di cui parli richiederà moltiplicazione e divisione, il che significa che per preservare l'esattezza dovrai utilizzare numeri razionali, che sono generalmente facili da implementare in aggiunta a un numero adeguato di numeri interi (cioè, di grandezza illimitata). (Common Lisp ha questi built-in, e non ci devono essere altre lingue.)

Ora, è necessario rappresentare radici quadrate di numeri arbitrari, e questi devono essere mescolati in.

Pertanto, un numero è uno di: un numero razionale, un numero razionale moltiplicato per una radice quadrata di un numero razionale (o, alternativamente, solo la radice quadrata di un razionale), o una somma di numeri. Per provare qualcosa, dovrai inserire questi numeri in una sorta di forma canonica, che per quanto riesca a capire può essere fastidioso e computazionalmente costoso.

Questo ovviamente significa che gli utenti saranno limitati a punti razionali e non possono utilizzare rotazioni arbitrarie, ma probabilmente non è importante.