GPS
Instructions
In this activity, you must write a program in RISC-V assembly language that computes your geographical coordinates in a bidimensional plane, based on the current time and messages received from 3 satellites.
Figure 6.2.1: Satellites' Positions on the Plane
To simplify the exercise, it is assumed that satellite A is placed at the origin of the cartesian plane (0, 0), while B and C are positioned at (0, YB) and (XC, 0), respectively. The satellites continuously send messages with a timestamp, which marks when the message was sent, via waves that propagate in all directions at a speed of 3 x 108 m/s. At a given time TR, you receive a message from each satellite containing the timestamps TA, TB, and TC. Assuming that all clocks are perfectly synchronized, print your coordinates (x, y) in the cartesian plane. Note that the formulation used in this exercise is not realistic.
Input
- Line 1 - Coordinates YB and Xc. Values are in meters, represented by 4-digit integers in decimal base and preceded by a sign ('+' or '-').
- Line 2 - Times TA, TB, Tc and TR. Values are in nanoseconds, represented by 4-digit integers in decimal base
Output
- Your coordinate - (x, y). Values are in meters, approximated, represented by 4-digit integers in decimal base and preceded by a sign ('+' or '-').
Examples
| Test Case | Input | Output |
|---|---|---|
| 1 | +0700 -01002000 0000 2240 2300 | -0088 +0016 |
| 2 | +1042 -20426823 4756 6047 9913 | -0902 -0215 |
| 3 | -2168 +02803207 5791 3638 9550 | +0989 -1626 |
| 4 | -2491 +09652884 7511 2033 9357 | -0065 -1941 |
| 5 | -0656 +13370162 2023 1192 9133 | +1255 -2381 |
Notes and Tips
- Multiple values written or read on/from the same line will be separated by a single space.
- Each line ends with a newline character '\n'.
- For this exercise, approximate solutions are accepted.
- Solutions with an absolute error smaller than 10 will be considered correct.
- The usage of the same method used in Exercise 6.1 with more iterations (e.g. 21 iterations) is recommended. Other methods to square root approximation can be used, as long as:
- It used only integers. Floating point numbers or the RISC-V square root instruction cannot be used.
- The approximation is as or more precise than the suggested method.
- It is best to work with distances in meters and time in nanoseconds, so that the provided input values do not cause overflow when using the proposed method and a good precision might be achieved.
- Problem Geometry:
- There are many ways to solve this exercise. Here, we propose an approach that uses the equation of a circle. Given that dA, dB and dC are the distances between your position and the satellites A, B and C, respectively:
- x2 + y2 = dA2 (Eq. 1)
- x2 + (y - YB)2 = dB2 (Eq. 2)
- (x - XC)2 + y2 = dC2 (Eq. 3)
- Using Equations 1 and 2:
- y = (dA2 + YB2 - dB2) / 2YB (Eq. 4)
- x = + sqrt(dA2 - y2) OR - sqrt(dA2 - y2) (Eq. 5)
- To find the correct x, you can try both possible values in Equation 3 and check which one is closer to satisfying the equation.
- There are many ways to solve this exercise. Here, we propose an approach that uses the equation of a circle. Given that dA, dB and dC are the distances between your position and the satellites A, B and C, respectively:
- You can test your code using the simulator's assistant from this link.