Reverse algorithm with tangent
Bart Van der Donck
Here is some code:
use Math::Trig;
my $v = 0.6235584253;
for (0..9) {
$v = $v + 1;
$v = tan ($v); # tangent
$v =~ s/\d{1,}\./0./; # no ^ for possible minus
}
print $v;
It prints -0.86659174554348. Is it logically/technically possible to
reverse this calculation ? In this example: start with
-0.86659174554348 and end up with 0.6235584253.
This topic was earlier started in sci.math, but no result.
(http://groups.google.com/group/sci.math/browse_frm/thread/2b7a2fd0737ffb28/)
Thanks,
--
Bart
jl_...@hotmail.com
>
> Here is some code:
>
> use Math::Trig;
> my $v = 0.6235584253;
> for (0..9) {
> $v = $v + 1;
> $v = tan ($v); # tangent
> $v =~ s/\d{1,}\./0./; # no ^ for possible minus
> }
> print $v;
>
> It prints -0.86659174554348. Is it logically/technically possible to
> reverse this calculation ? In this example: start with
> -0.86659174554348 and end up with 0.6235584253.
Dear Bart,
I would think that it's not possible to logically reverse this
calculation, and here's why I think so:
Every time you loop you set $v to its tangent ( with $v = tan($v); )
and then mod it by 1. Let's just say, for the sake of argument, that
the first time through the loop tan($v) evaluates to 1.5 . The very
next line would set $v to 0.5 .
But now let's assume that $v was a greater value, one that would
make tan($v) evaluate to 2.5 . The very next line would still set $v
to 0.5 .
In fact, there are an infinite number of unique values that would
make tan($v) evaluate to 1.5, 2.5, 3.5, 4.5, 5.5, etc. -- which would
all make $v become 0.5 in the very next line.
Therefore, if you're reversing this algorithm, it would be
impossible to know which of those values is the right one to obtain
when reversing the line that performs the mod 1 operation. And that's
why I don't think it's possible to reverse this calculation.
(But then again, I could be wrong... ;)
I hope this helps, Bart.
-- Jean-Luc
Michele Dondi
wrote:
>It prints -0.86659174554348. Is it logically/technically possible to
>reverse this calculation ? In this example: start with
>-0.86659174554348 and end up with 0.6235584253.
How 'bout atan()?
Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
.'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,
Peter J. Holzer
> Here is some code:
>
> use Math::Trig;
> my $v = 0.6235584253;
> for (0..9) {
> $v = $v + 1;
> $v = tan ($v); # tangent
> $v =~ s/\d{1,}\./0./; # no ^ for possible minus
> }
> print $v;
>
> It prints -0.86659174554348. Is it logically/technically possible to
> reverse this calculation ? In this example: start with
> -0.86659174554348 and end up with 0.6235584253.
I don't think so: This function isn't smooth and it doesn't even have
smooth intervals of any useful length.
> This topic was earlier started in sci.math, but no result.
> (http://groups.google.com/group/sci.math/browse_frm/thread/2b7a2fd0737ffb28/)
There you relaxed the requirements a bit: You don't need to get back to
0.6235584253, it is enough to find any value which when fed into your
function gives the result -0.86659174554348.
This makes it a lot easier. We know that at the start and end of each
loop $v has a value between -1 and 1, and that the tan function has a
periodicity of pi. So we can reverse your function like this:
#!/usr/bin/perl
use warnings;
use strict;
use Math::Trig;
sub f {
my ($v) = @_;
for (0..9) {
$v = $v + 1;
$v = tan ($v); # tangent
$v =~ s/\d{1,}\./0./; # no ^ for possible minus
}
return $v;
}
sub rf {
my ($v) = @_;
for (0 .. 9) {
my $s = $v >= 0 ? 1 : -1;
FIND_INT:
for my $i (0 .. 100) { # should really be 0 .. infinity
my $vx = $v + $i * $s;
$vx = atan2($vx, 1);
if (abs ($vx - 1) < 1) {
$v = $vx - 1;
last FIND_INT;
} elsif (abs ($vx + pi - 1) < 1) {
$v = $vx + pi - 1;
last FIND_INT;
}
}
}
return $v;
}
my $v = 0.6235584253;
print $v, "\n";
$v = f($v);
print $v, "\n";
$v = rf($v);
print $v, "\n";
$v = f($v);
print $v, "\n";
Which prints:
0.6235584253
-0.86659174554348
-0.217377922712057
-0.86659174566011
is -0.86659174566011 close enough to -0.86659174554348 for your
purposes?
Note that the rf function returns a value between -1 and 1, although you
specified that the original value is between 0 and 1. Modifying it to
produce a result between 0 and 1 is left as an exercise for the reader
:-).
hp
--
_ | Peter J. Holzer | > Wieso sollte man etwas erfinden was nicht
|_|_) | Sysadmin WSR | > ist?
| | | h...@hjp.at | Was sonst wäre der Sinn des Erfindens?
__/ | http://www.hjp.at/ | -- P. Einstein u. V. Gringmuth in desd
Bart Van der Donck
> On 2006-10-21 15:59, Bart Van der Donck <ba...@nijlen.com> wrote:
> > Here is some code:
> >
> > use Math::Trig;
> > my $v = 0.6235584253;
> > for (0..9) {
> > $v = $v + 1;
> > $v = tan ($v); # tangent
> > $v =~ s/\d{1,}\./0./; # no ^ for possible minus
> > }
> > print $v;
> >
> > It prints -0.86659174554348. Is it logically/technically possible to
> > reverse this calculation ? In this example: start with
> > -0.86659174554348 and end up with 0.6235584253.
> > [...]
> > (http://groups.google.com/group/sci.math/browse_frm/thread/2b7a2fd0737ffb28/)
>
> There you relaxed the requirements a bit: You don't need to get back to
> 0.6235584253, it is enough to find any value which when fed into your
> function gives the result -0.86659174554348.
>
> This makes it a lot easier. We know that at the start and end of each
> loop $v has a value between -1 and 1, and that the tan function has a
> periodicity of pi. So we can reverse your function like this:
> [snip code]
Thanks for the code, it's further than I got. I think you're absolutely
right that a lot changes when the requirement is only to return 'any'
start value, not 'the' start value. The real-world background is
password encryption algorithms here, so the 'any' start value suits
indeed.
I believe the core of this problem is the line where it says:
$v =~ s/\d{1,}\./0./;
(in maths: v = v % 1), because at this point something is 'dropped',
namely the found digits before the dot (or, in Perl, the $1-variable of
the regex). It can't be retrieved anymore, but, for an exact reverse to
the same start value, that is an absolute requirement. Probably there
must exist some logical/mathematical term for such phenomenons. My
conclusion at this point would be that the same start value cannot be
obtained anymore.
(One workaround could be to push the $1's to an array and use that
array in the reverse-routine, but this would of course be a fallacy
since the start value must be known in order to fill the array).
But that doesn't say anything about whether or not the 'any' start
value can be fetched indeed.
> Which prints:
> 0.6235584253
> -0.86659174554348
> -0.217377922712057
> -0.86659174566011
> is -0.86659174566011 close enough to -0.86659174554348 for your
> purposes?
Unfortunately, no. It must be further parsed to a character string
which needs the exact digits after the dot (minus or not doesn't
matter).
The first thing that comes to mind is the accuracy of Math::Trig's
tan() and atan() functions, because it must be extremely precise for
the repeated tan()/atan() calls.
Maybe you've written the right code. I need some time to study that. I
see exactly the same results as you, so I'ld say it's probably not
related to the OS. Maybe Perl or Math::Trig blocks off after a certain
range of digits, or it has something to do with
http://faq.perl.org/perlfaq4.html#Why_am_I_getting_lon
> Note that the rf function returns a value between -1 and 1, although you
> specified that the original value is between 0 and 1. Modifying it to
> produce a result between 0 and 1 is left as an exercise for the reader
> :-).
Can do! :-)
--
Bart
Peter J. Holzer
> On 21 Oct 2006 08:59:58 -0700, "Bart Van der Donck" <ba...@nijlen.com>
> wrote:
>>It prints -0.86659174554348. Is it logically/technically possible to
>>reverse this calculation ? In this example: start with
>>-0.86659174554348 and end up with 0.6235584253.
>
> How 'bout atan()?
Doesn't help by itself: His function contains two non-injective
periodic functions (tan() and %) and each is applied 10 times. This
means that there are Infinity**20 possible values in the domain which
map to the same value in the range.
I've outlined a way to get one of these values in a different post (I do
use atan2, but that's the simple part).
Ilya Zakharevich
Bart Van der Donck
<ba...@nijlen.com>], who wrote in article <1161462300.6...@f16g2000cwb.googlegroups.com>:
> > is -0.86659174566011 close enough to -0.86659174554348 for your
> > purposes?
>
> Unfortunately, no. It must be further parsed to a character string
> which needs the exact digits after the dot (minus or not doesn't
> matter).
tan' is always 1 or more; thus your "encryption" function also has
derivative of 1 or more. Hence the "decryption" function has
derivative 1 or less.
Essentially, what it means in this example is that there is no "loss
of precision"; given 39 digits after the point in the encrypted value,
you should expect to completely restore 39 digits after the poinit in
the decrypted value. All you need is doing calculation with high
enough precision, so the errors do not accumulate.
So do the calcs in some higher-precision-math Perl module.
[Of course, what I said depends a lot on the fact that only 10 rounds
of calculation are made, thus there are significantly long intervals
of smoothness; I would not be surprised if about 40 rounds these
intervals would decrease to be short enough to contain at most 1
exactly representable in `double' number...]
Hope this helps,
Ilya
Michele Dondi
<hjp-u...@hjp.at> wrote:
>Doesn't help by itself: His function contains two non-injective
>periodic functions (tan() and %) and each is applied 10 times. This
Indeed, hadn't actually read the full post, and in particular the
actual code, just noticed an application of tan() and a sign trick.
Apologies for raising the noise/signal ratio.
Peter J. Holzer
The function is not "injective".
(Note that tan isn't injective in the general case, either. However,
since it gets only input values between 0 and 2 in your code, it is,
except possibly for values very close to pi/2)
[...]
>> Which prints:
>> 0.6235584253
>> -0.86659174554348
>> -0.217377922712057
>> -0.86659174566011
>> is -0.86659174566011 close enough to -0.86659174554348 for your
>> purposes?
>
> Unfortunately, no. It must be further parsed to a character string
> which needs the exact digits after the dot (minus or not doesn't
> matter).
>
> The first thing that comes to mind is the accuracy of Math::Trig's
> tan() and atan() functions, because it must be extremely precise for
> the repeated tan()/atan() calls.
>
> Maybe you've written the right code. I need some time to study that. I
> see exactly the same results as you, so I'ld say it's probably not
> related to the OS. Maybe Perl or Math::Trig blocks off after a certain
> range of digits,
It certainly does: IEEE-754 double precision floating point numbers have
53 bits of precision. Even if the tan and atan functions are as precise
as possible (the relative error is less than 2**-54), the rounding
errors add up quite a bit.
Actually, I don't think tan and atan are that precise: These functions
are computed by a series, and I believe that normally only a small
fixed number of elements in the series is computed. The manual for your
CPU might tell you the maximum error for certain number ranges. I would
not be surprised if different CPUs[0] produce different results.
I see two possible ways to improve the code:
1) For each step, make sure that the computed value matches exactly.
If it doesn't it may be possible to compute a better value with
Newton's method. If there isn't, skip it.
2) Check the final computed value. If it doesn't match, backtrack.
hp
[0] For completeness, here's /proc/cpuinfo of my laptop:
vendor_id : GenuineIntel
cpu family : 6
model : 8
model name : Pentium III (Coppermine)
stepping : 10
Bart Van der Donck
> [...]
> tan' is always 1 or more; thus your "encryption" function also has
> derivative of 1 or more. Hence the "decryption" function has
> derivative 1 or less.
>
> Essentially, what it means in this example is that there is no "loss
> of precision"; given 39 digits after the point in the encrypted value,
> you should expect to completely restore 39 digits after the poinit in
> the decrypted value. All you need is doing calculation with high
> enough precision, so the errors do not accumulate.
>
> So do the calcs in some higher-precision-math Perl module.
I've a feeling that this must be the core of the problem, yes. I just
hope it's possible to perform such hi-res calculations in the first
place. My conclusion at this point is that Peter's code does the job,
but has a precision problem with the tan2()-call. I'll see what's
available at CPAN, or otherwise (try to) write it myself.
--
Bart
Ilya Zakharevich
Bart Van der Donck
> > Essentially, what it means in this example is that there is no "loss
> > of precision"; given 39 digits after the point in the encrypted value,
> > you should expect to completely restore 39 digits after the poinit in
> > the decrypted value. All you need is doing calculation with high
> > enough precision, so the errors do not accumulate.
> > So do the calcs in some higher-precision-math Perl module.
> I've a feeling that this must be the core of the problem, yes. I just
> hope it's possible to perform such hi-res calculations in the first
> place.
No NEED to. Alternatively, since you know the approximate answer, it
is easy to increase its precision by binary search. Your function is
monotonic, after all (on small intervals)...
Yours,
Ilya
P.S. Answering some other post: tan() IS injective on the intervals
in question; but the FP approximation is not injective.
E.g., near 0 tan(x) behaves very similar to (1+eps)*x for a very
small eps. So an interval of length delta is mapped to an
interval practically the same length.
Take such an interval near AND BELOW 2**(-n) so that tan(x) is
near AND ABOVE 2**(-n). We get a mapping which sends an
interval of length delta to an interval of length (1+eps)delta;
but the latter interval contains approx. 1/2 of the number of
exactly representable floating point values of the former
interval.
Bart Van der Donck
[IZ]
>>> So do the calcs in some higher-precision-math Perl module.
[BVdD]
>> I've a feeling that this must be the core of the problem, yes. I just
>> hope it's possible to perform such hi-res calculations in the first
>> place.
[IZ]
> No NEED to. Alternatively, since you know the approximate answer, it
> is easy to increase its precision by binary search. Your function is
> monotonic, after all (on small intervals)...
> [...]
Yes. As per my test:
START VALUE CRYPTED DECRYPTED CRYPTED BACK
0.235689444576 -0.02695168550062 -0.217378385791554 -0.02695168552053
0.864201354575 -0.3410699000001 -0.217376072921599 -0.34106990007059
0.840037468 -0.52586445007622 -0.217376789431016 -0.52586445014133
0.23 0.62204008845158 0.994466053557457 0.622040088514515
0.540398781463 0.299718068673499 0.994464173617474 0.29971806865337
0.5778 0.625447420438520 0.994466072360211 0.625447420458046
0.568846 0.2893342697752 0.994464111168694 0.289334269649148
0.21468554 0.0445961802164 0.994462664098794 0.0445961802353584
0.5 0.16452058233646 0.994463363559315 0.164520582231663
0.1684596 -0.1927399763699 -0.217375435678833 -0.1927399764223
0.9475677 0.660203288614217 0.994466262430239 0.660203288737099
0.5894 0.51818577586632 0.994465467150153 0.518185775862764
(*) 0.82416378434687 0.99446711342503 0.824163784296701
(**) 0.9195906682233 0.994467571813756 0.919590668184188
(***) 0.0876330835002718 0.994462911781017 0.0876330834905578
(*) 0.5684672556894522455565423897512444359445
(**) 0.21038994750369854123559425103247680941
(***) 0.647583591374853694423130214
This table seems to indicate that the first nine digits after the dot
always match.
Say we throw away anything after that, and write a "brute force"-loop
like this (supposed we start at 0.123456789):
0.1234567891
0.1234567892
...
0.1234567899
0.12345678911
0.12345678912
...
0.12345678919
0.12345678921
...
0.12345678929
et cetera untill we have a match. In order to avoid endless loops in
case anything goes wrong, one could stop at, let's say 10,000,000 loops
or so. (Which would have checked 0.12345678910000000 to
0.12345678919999999, which would normally return our result I'ld say,
based on the table above).
Another observation is that the DECRYPTED-column always appears to
start with -0.21737* or 0.99446*. I have absolutely no idea why.
--
Bart
Ilya Zakharevich
Bart Van der Donck
> Another observation is that the DECRYPTED-column always appears to
> start with -0.21737* or 0.99446*. I have absolutely no idea why.
The "1-round-decrypt" function has derivative below 1, so it sends an
interval (inside its regions of continuity) to a shorter interval; in
fact, in many cases *much* shorter interval. It should also have a
point of discontinuity, so the (initial?) round sends the (initial)
interval into two short intervals. The following rounds decreases the
lengths of these two intervals yet more.
Hope this helps,
Ilya
Bart Van der Donck
> [...]
> I see two possible ways to improve the code:
>
> 1) For each step, make sure that the computed value matches exactly.
> If it doesn't it may be possible to compute a better value with
> Newton's method. If there isn't, skip it.
Here is my meager attempt. In the first place, Math::Trig's tan()
differs from that in my original encryption (other implementation).
Sorry that I have to come up with this at this point.
The original encryption returns a tangent like this:
0.0000000000000000
while Math::Trig returns
0.00000000000000
This causes a significantly different encrypted result.
As for the decryption, I have played around with very precise tangent
calls. I'm using MySQL4's TAN (which can be customized how many digits
to return, up to 0.000000000000000000000000000000).
----------------------------------------------------------------------
#!/usr/bin/perl
use warnings;
use strict;
use Math::Trig;
use DBI;
sub f {
my ($v) = @_;
for (0..9) {
$v = $v + 1;
my $db = DBI->connect("DBI:mysql:NAME:HOST","USR","PW");
# must use 0.0000000000000000 here
my $query = $db->prepare("SELECT TAN($v)+0.0000000000000000");
$query->execute;
while (my @array = $query->fetchrow_array) {
$v = $array[0]; }
$query->finish;
$db->disconnect;
$v =~ s/\d{1,}\./0./; # no ^ for possible minus
}
return $v;
}
sub rf {
my ($v) = @_;
for (0 .. 9) {
my $s = $v >= 0 ? 1 : -1;
FIND_INT:
for my $i (0 .. 100) { # should really be 0 .. infinity
my $vx = $v + $i * $s;
my $db = DBI->connect("DBI:mysql:NAME:HOST","USR","PW");
# use 0.000000000000000000000000000000 for max accuracy
my $query =
$db->prepare("SELECT
ATAN2($vx,1)+0.000000000000000000000000000000");
$query->execute;
while (my @array = $query->fetchrow_array) {
$vx = $array[0]; }
$query->finish;
$db->disconnect;
if (abs ($vx - 1) < 1) {
$v = $vx - 1;
last FIND_INT;
} elsif (abs ($vx + pi - 1) < 1) {
$v = $vx + pi - 1;
last FIND_INT;
}
}
}
return $v;
}
my $v = 0.6235584253;
print $v, "\n";
$v = f($v);
print $v, "\n";
$v = rf($v);
print $v, "\n";
$v = f($v);
print $v, "\n";
__END__
----------------------------------------------------------------------
Output:
0.6235584253
-0.8666340060134772
-0.217377922839505
-0.8666340058771898
While your output was:
0.6235584253
-0.86659174554348
-0.217377922712057
-0.86659174566011
So it gets longer (which I had expected), but not preciser (which I had
not expected).
Also... can Math::Trig's PI be trusted to be precise enough ? Setting
it manually to 3.141592653589793115997963468544 doesn't seem to make a
difference.
--
Bart
Peter J. Holzer
>>
>> 1) For each step, make sure that the computed value matches exactly.
>> If it doesn't it may be possible to compute a better value with
>> Newton's method. If there isn't, skip it.
>
> Here is my meager attempt. In the first place, Math::Trig's tan()
> differs from that in my original encryption (other implementation).
> Sorry that I have to come up with this at this point.
>
> The original encryption returns a tangent like this:
>
> 0.0000000000000000
>
> while Math::Trig returns
>
> 0.00000000000000
I'd guess that neither returns a decimal number: Probably both return a
binary FP number. Using a decimal representation of such a number to
determine whether they are equal may be misleading.
(Also note that your "convert to decimal and replace digits before the
period with 0" operation is not the same as fmod, unlike the latter it
includes two rounding steps)
Is your "other implementation" also in Perl? If it isn't, you must be
extra careful if duplicating its exact functionality.
> This causes a significantly different encrypted result.
>
> As for the decryption, I have played around with very precise tangent
> calls. I'm using MySQL4's TAN (which can be customized how many digits
> to return, up to 0.000000000000000000000000000000).
I doubt that. MySQL almost certainly uses double precision for
trigonometric functions, so the result won't be accurate for more than
about 16 decimal digits. Even if it uses extended precision that's only
about 19 decimal digits (on Intel x87 compatible processors). You may
see more digits, but they don't represent real accuracy. For comparison,
try:
perl -MMath::Trig -e 'printf("%.60f\n", tan(1))'
1.557407724654902070327011642802972346544265747070312500000000
That looks like it is accurate to 53 decimal digits, but it isn't -
tan(1.0000000000000001)) returns exactly the same value, but
tan(1.00000000000000015)) returns
1.557407724654902958505431342928204685449600219726562500000000
which differs in the 17th decimal digit, or (if you look at both numbers
in binary) in the 50th bit. So you don't actually get more than about 15
decimal places of accuracy (possibly even less).
> Also... can Math::Trig's PI be trusted to be precise enough ? Setting
> it manually to 3.141592653589793115997963468544 doesn't seem to make a
> difference.
See above: You have 53 bits of precision - writing more digits won't
help as they will be ignored. (Unless you use a BigNum package)
hp