Find first integer pair given two angles

[Darryl]

Hey Guys

How do I go about finding the first integer pair that falls between two angles, especially if the angle is really small for instance:

If I have two lines (rays?) A and B, extending from the origin.

A = 13.00000000001 degrees
B = 13.00000000002 degrees

How do I find an integer point that falls between them? If it makes a difference, it's allowed to fall on line A but not on B.

Thanks
Darryl

[ventsyv]

Hmmm very interesting. You can try the brute force approach and just do a double loop and go over all possible integer combinations (in a given range ofcourse).

So lets say you have the point (3,4) then to get the angle, you take arctan(4/3) and if A <= arctan(4/3) <= B (A & B being your rays where ray B has higher angle than A) you've got your point.

Now, you can optimize in several ways:
1. Look at the quadrants your angles lay in. For example if both A & B are in quadrant 1, you need not consider any negative values.
2. Lets go back to the (3,4) point. Lets say actan(4/3) < A and B > A.
In this case incrementing X won't do you any good (again assuming quadrant 1) so you need to increment Y.
If arctan(4/3) > B then you need to increment X.

Now this whole approach assumes you can limit your X & Y values and probably won't work very well if the difference between the angles is very very small (as it is in your example).

[Darryl]

Arctan...that was simple, didn't know you could calculate the angle that easily. Seem like I remember having to use sin and or cos, but that was over 20 years ago!

@1. I had thought about this and figured I'd only need to increase the absolute values, then apply the signs, dependent on the quadrant.

@2. Unfortunately I can't limit X and Y, though I am trying to at least limit them to what c++ can easily handle, ie. int64, but may end up using GMP, especially in light of the fact because the angles will probably get much smaller than my example, I will need it for that.


One other idea I have since the angles will infinitely spread, that if I figured out where they reach a distance of 1 unit apart, that extending them another 1 unit in length would surely enclose a integer pair, however it would miss all earlier integer pairs which I really would like instead for instance.

A= 44.99999999999999999999999
B= 45.00000000000000000000001

Would enclose 1,1 (desired answer) but if I used my method above, who knows how far I'd be out.

[ventsyv]

One other idea I have since the angles will infinitely spread, that if I figured out where they reach a distance of 1 unit apart, that extending them another 1 unit in length would surely enclose a integer pair, however it would miss all earlier integer pairs which I really would like instead for instance.

If you find a easy way to do that, you can use this point as an upper limit of your search space. (That way your X and Y won't need to go over the values for that point.)

[ventsyv]

Hmm here is a different idea.

Starting at the origin and moving along the X axis (in positive direction)
Take tan of A and tan of B. Now tangent is just a ration of Y/X but since you know X, you can easily find what Y is.
That would give you your Y coordinate of the point on each ray.
Now check if integer exists such that Y1<= Int <= Y2 (where Y1= X1 * tan(A), Y2= X2* tan(B), X1=X2). The first one you find is your Y coordinate and the X coordinate you already know since you are moving from left to right on the X axis.

[Darryl]

I like this last idea, ....but I am gonna change the requirements on you (hopefully make it easier, with a bit of an explanation of what I am trying to do)

I have a process which returns a upper and lower angle. These angles are of very high precision. But for my purposes I can use any angle in-between these two angles.

One test I just tried had the difference between upper and lower bound at 9.136e-114

So to store this angle would be quite an undertaking, so I figured if I can find a point contained in it, it would be easy to store that point and later recreate the angle when needed.

So the change in requirement is just to find any point that falls in between the 2 angles but fits in a c++ double type or smaller.

*** Edit

Building on what you've said, I can go along the x axis, in integer increments, get the 2 Y values and then figure if the is a unique double between them.

[Alvaro]

A typical range of angles of size 9.136e-114 doesn't contain any numbers that can be represented in any encoding using 64 bits. Just think about how many disjoint ranges of angles of that size one can find (in the order of 10^115 of them). At most 2^64 of those ranges contain a number that you can represent using 64 bits. That's about 1 in every 10^95 ranges.

The GMP library provides a type for arbitrarily precise real numbers. I would try to use that.

If you still want to find one fraction in that range whose slope is in a particular range (in between the tangent of the two limiting angles), pick a slope that is the average of the two limiting slopes and look at the truncated continuing fractions for that number. At some point they will be close enough to the number that it will be in your range. I can provide an example if that was too confusing.

[Darryl]

A typical range of angles of size 9.136e-114 doesn't contain any numbers that can be represented in any encoding using 64 bits.

I realize this, that's why I am trying to find a fraction whose slope falls in between the 2 angles ( I liked how you put it) ***doh edit*** wait you are saying that I won't even find a fraction ( or very unlikely too) that can decribe a slope that falls in between.

I am using GMP and I still want to find one fraction whose slope falls in the range of the 2 given angles.

1. pick a slope that is the average of the two limiting slopes.
A+B/2 = average angle, OK I got that

2. look at the truncated continuing fractions for that number...uhh you kind of lost me here.... how do I get the fraction....putting this with what ventsyv said to a pick a fraction ie 1/2 and if it falls below, increase numerator and above, increase denominator?

[Alvaro]

Take a look here: http://en.wikipedia.org/wiki/Continued_fraction ; in particular, the section called Best_rational_approximations explains why I have hopes of having good results with this method.

As an example, if you want a point in the angle between 13.00000000001 and 13.00000000002 degrees, I would do:
A = tan(13.00000000001) = .23086819112574694729
B = tan(13.00000000002) = .23086819112593078283
X = (A+B)/2 = .23086819112583886506

X = 0+1/(4+1/(3+1/(59+1/(2+1/(16+1/(1+1/(3+1/(1+1/(3+1/(1+1/(2+1/(1+...))))))))))))
If we truncate the expression there, you get a rational approximation to X (564750/2446201) which is at an angle of 13.00000000001014880495 degrees.

http://134.59.10.148/wims/wims.cgi?sess ... um_style=1

EDIT: The last approximation in that webpage is 1007466802/4363818147, which is at an angle of atan(1007466802/4363818147)/p*180 = 13.00000000001499999983913466568...

As you see, you quickly get very large numbers, but you get very very good approximations.

[Darryl]

Compression is hard, let's go shopping!

Ok I am gonna let the cat out the back, this is another one of my compression schemes.

Here is the basic algorithm, basically to adjust the upper and lower bound according to whether next bit was 0 or 1, thus focusing on a smaller and smaller angle.

I hope the beauty of the plan was to be even at ridiculously small angles, I could extend them out far enough, to capture a coordinate pair, that could be stored more efficiently than the original bitstream or angle it describes. But now I am having second thoughts...you know it's easy to imagine this would work when you picture a tiny angle that encloses a 45 degree angle, but I guess for other angles, it won't be so nice.

Code: Select all

#include <iostream>
#include <string>
#include "gmpxx.h"
#include <cmath>


mpf_class lowerbound(0.0, 512);
mpf_class upperbound(360.0,512);

std::string test = "10010100100101110100";\\edited from a 1024 digit binary string

int main()
{
   for (int index = 0; index < test.size(); index++)
   {
      mpf_class newbound((lowerbound+upperbound)/2.0,512);
      if (test[index] == '1')
      {
         lowerbound = newbound;
      }
      else
      {
         upperbound = newbound;
      }   
      
   }
}


[Alvaro]

Sorry to break the bad news, but this has no chance of working whatsoever. A compression algorithm only works because not all messages have equal probability. You then try to encode all the unlikely messages using a few more bits, and the likely messages using fewer bits. If your compression idea doesn't involve compressing well only the most likely messages, then it won't work.

[ventsyv]

Here is the basic algorithm, basically to adjust the upper and lower bound according to whether next bit was 0 or 1, thus focusing on a smaller and smaller angle.

I hope the beauty of the plan was to be even at ridiculously small angles, I could extend them out far enough, to capture a coordinate pair, that could be stored more efficiently than the original bitstream or angle it describes. But now I am having second thoughts...you know it's easy to imagine this would work when you picture a tiny angle that encloses a 45 degree angle, but I guess for other angles, it won't be so nice.

You lost me there . You are trying to create an algorithm that will compress a bunch of coordinate points and store them as angles ???

[Darryl]

Start with a circle, say with a radius 1, divide it in half, top half is 0, bottom half is 1

put another circle with radius 2 around that, and divide it by 4, with each section alternating 0 and 1,

keep adding larger circles and keep doubling the subdivisions.

Now if you start at the origin and start traveling down a ray of a particular angle, as you cross each bigger circle you add that bit to your decoded stream.

So any program starting with the first bit 1 will fall between 180 and 360, if the second bit is 1, then it narrows to 270 and 360, if the third bit is 0, it will be between 270 and 315, etc, etc

Now, for instance I could say, my program is 1 gigabyte long and the angle that represents it is 45.0125564589401560540998401 I could travel down the ray and as I pass each bigger circle, calculate whether it's crossing a 1 section or a 0 section until I've recreated the program.

The only problem is that the angle that would represent a 1 gig program would probably take one gig of storage to store the precision.

[ventsyv]

Hmm, interesting idea. 1Gb = 2^1000 bytes (right ?) so you'll have to do 1000 divisions of your circle.
You'll have to calculate what the max representation is and how much memory it will be required to hold that representation.

As Alvaro said, the traditional approach is to search for common patterns and represent them by ever increasing in size bite sequence where the most common patterns get the shortest byte code and as the sequences get less and less likely the byte code increases.

I don't see that in your idea. In essence your idea is equivelent to taking the original data and casting it to a double (or whatever can hold that kind of precision). For each bit you'll have to do one division, which is basically equivelent to that bit (ofcourse 1 bit can represent 2 distinct posibilities ).

But give it a try, there might be something I'm missing.

[Alvaro]

But give it a try, there might be something I'm missing.

No, you are not missing anything. The only purpose of trying would be to develop better intuitions about how compression works (or doesn't).