in reply to RPN Question

Although this is not really what you are asking for, another approach for such equation solving, frequently employed in math libraries, is to guess a value and make successive improvements to get closer and closer approximations of the target number.

I thought that it would take me 15 minutes to show an example, but it turned out that it took me an hour and a half, because of some initial mistakes on my part due to the fact that I was not entirely clear in my mind on what exactly I needed to do.

It could probably be simpler, this is very imperfect and not tested against all kinds of cases, but anyway, this gives an idea of the approach: 


use strict;
use warnings;
use feature "say";
use constant DEBUG => 1;

my $epsilon = 1e-12; # precision
my ($result, $step) = (0, 10); # arbitrary start values
my $equation = "(2*(4*x-8)+3*x)-(10*x+1-9)"; # " = 0" omitted
$equation =~ s/x/\$x/g;
my $eval = create_eval($equation); # currying the equation for simplic
+ity

my $debug = 1;
while (1) {
    my $val = $eval->($result);
    last if abs $val < $epsilon;
    my $new_result = $result + $step;
    my $temp = $eval->($new_result);
    say "x = $result ; val = $val ; temp = $temp; step = $step" if DEB
+UG;
    $result = $new_result and last if abs $temp < $epsilon;
    if ($temp == $val) {
        say "No solution for this equation";
        undef $result;
        last;
     }
    if (($val > 0 and $temp < 0) or ($val < 0 and $temp > 0)) {
        while (1) {
            $step = 0;
            my $avg = ($result + $new_result) /2;
            my $avg_val = $eval->($avg);
            # say "x = $result; val = $val ; temp = $temp; step = $ste
+p; avg = $avg" if DEBUG;
            printf "%s%.15f%s%.15f%s%.15f%s%.15f\n", "x = ", $result, 
+" val = ", $val, " temp = ", $temp, " avg = ", $avg;
            $new_result = $avg and last if abs $avg_val < $epsilon;
            if ($avg_val > 0) {
                $result = $avg and $val= $avg_val if $val > 0;
                $new_result = $avg and $temp = $avg_val if $temp > 0;
            } else {
                $result = $avg and $val = $avg_val if $val < 0;
                $new_result = $avg and $temp = $avg_val if $temp < 0;
            }
        }
    }                        
    $step = -$step and next if $temp < $val and $val < 0;
    $step /= 2 and next if abs $temp > abs $val;      # we are further
+ from 0, reduce step by half
    $result =$new_result;      # $temp is closer to 0, let's continue 
+with $new_resultp
    
}

printf "%s%.10f\n", "Result is: ", $result;# if defined $result;

sub create_eval {
    my $formula = shift;
    return sub { my $x = shift; return eval($formula);}
}

[download]
The result I get is 8.00000..., so the same as the RPN unraveling by Anonymous Monk, except of course that I do not get an integer but a floating point number.

Just to see the successive approximations, this is the debugging printout. 

$ perl solver.pl
x = 0 ; val = -8 ; temp = 2; step = 10
x = 0.000000000000000 val = -8.000000000000000 temp = 2.00000000000000
+0 avg = 5.000000000000000
x = 5.000000000000000 val = -3.000000000000000 temp = 2.00000000000000
+0 avg = 7.500000000000000
x = 7.500000000000000 val = -0.500000000000000 temp = 2.00000000000000
+0 avg = 8.750000000000000
x = 7.500000000000000 val = -0.500000000000000 temp = 0.75000000000000
+0 avg = 8.125000000000000
x = 7.500000000000000 val = -0.500000000000000 temp = 0.12500000000000
+0 avg = 7.812500000000000
x = 7.812500000000000 val = -0.187500000000000 temp = 0.12500000000000
+0 avg = 7.968750000000000
x = 7.968750000000000 val = -0.031250000000000 temp = 0.12500000000000
+0 avg = 8.046875000000000
x = 7.968750000000000 val = -0.031250000000000 temp = 0.04687500000000
+0 avg = 8.007812500000000
x = 7.968750000000000 val = -0.031250000000000 temp = 0.00781250000000
+0 avg = 7.988281250000000
x = 7.988281250000000 val = -0.011718750000000 temp = 0.00781250000000
+0 avg = 7.998046875000000
x = 7.998046875000000 val = -0.001953125000000 temp = 0.00781250000000
+0 avg = 8.002929687500000
x = 7.998046875000000 val = -0.001953125000000 temp = 0.00292968750000
+0 avg = 8.000488281250000
x = 7.998046875000000 val = -0.001953125000000 temp = 0.00048828125000
+0 avg = 7.999267578125000
x = 7.999267578125000 val = -0.000732421875000 temp = 0.00048828125000
+0 avg = 7.999877929687500
x = 7.999877929687500 val = -0.000122070312500 temp = 0.00048828125000
+0 avg = 8.000183105468750
x = 7.999877929687500 val = -0.000122070312500 temp = 0.00018310546875
+0 avg = 8.000030517578125
x = 7.999877929687500 val = -0.000122070312500 temp = 0.00003051757812
+5 avg = 7.999954223632812
x = 7.999954223632812 val = -0.000045776367188 temp = 0.00003051757812
+5 avg = 7.999992370605469
x = 7.999992370605469 val = -0.000007629394531 temp = 0.00003051757812
+5 avg = 8.000011444091797
x = 7.999992370605469 val = -0.000007629394531 temp = 0.00001144409179
+7 avg = 8.000001907348633
x = 7.999992370605469 val = -0.000007629394531 temp = 0.00000190734863
+3 avg = 7.999997138977051
x = 7.999997138977051 val = -0.000002861022949 temp = 0.00000190734863
+3 avg = 7.999999523162842
x = 7.999999523162842 val = -0.000000476837158 temp = 0.00000190734863
+3 avg = 8.000000715255737
x = 7.999999523162842 val = -0.000000476837158 temp = 0.00000071525573
+7 avg = 8.000000119209290
x = 7.999999523162842 val = -0.000000476837158 temp = 0.00000011920929
+0 avg = 7.999999821186066
x = 7.999999821186066 val = -0.000000178813934 temp = 0.00000011920929
+0 avg = 7.999999970197678
x = 7.999999970197678 val = -0.000000029802322 temp = 0.00000011920929
+0 avg = 8.000000044703484
x = 7.999999970197678 val = -0.000000029802322 temp = 0.00000004470348
+4 avg = 8.000000007450581
x = 7.999999970197678 val = -0.000000029802322 temp = 0.00000000745058
+1 avg = 7.999999988824129
x = 7.999999988824129 val = -0.000000011175871 temp = 0.00000000745058
+1 avg = 7.999999998137355
x = 7.999999998137355 val = -0.000000001862645 temp = 0.00000000745058
+1 avg = 8.000000002793968
x = 7.999999998137355 val = -0.000000001862645 temp = 0.00000000279396
+8 avg = 8.000000000465661
x = 7.999999998137355 val = -0.000000001862645 temp = 0.00000000046566
+1 avg = 7.999999999301508
x = 7.999999999301508 val = -0.000000000698492 temp = 0.00000000046566
+1 avg = 7.999999999883585
x = 7.999999999883585 val = -0.000000000116415 temp = 0.00000000046566
+1 avg = 8.000000000174623
x = 7.999999999883585 val = -0.000000000116415 temp = 0.00000000017462
+3 avg = 8.000000000029104
x = 7.999999999883585 val = -0.000000000116415 temp = 0.00000000002910
+4 avg = 7.999999999956344
x = 7.999999999956344 val = -0.000000000043656 temp = 0.00000000002910
+4 avg = 7.999999999992724
x = 7.999999999992724 val = -0.000000000007276 temp = 0.00000000002910
+4 avg = 8.000000000010914
x = 7.999999999992724 val = -0.000000000007276 temp = 0.00000000001091
+4 avg = 8.000000000001819
x = 7.999999999992724 val = -0.000000000007276 temp = 0.00000000000181
+9 avg = 7.999999999997272
x = 7.999999999997272 val = -0.000000000002728 temp = 0.00000000000181
+9 avg = 7.999999999999545
Result is: 8.0000000000

[download]

Je suis Charlie.

Replies are listed 'Best First'.
Re^2: Reverse Polish Notation Question
by hdb (Monsignor) on May 02, 2015 at 11:56 UTC

    Two comments:

    From $temp == $val, you cannot conclude that there is no solution, unless you explicitly assume that we have a linear equation, ie a straight line.

    If you would calculate the slope from the first two values, you can guess quite well where the solution is, especially for a linear equation.

[reply]
[d/l]
      Thank you hdb for your comments.

      As for the first comment, we have a first degree equation, so, yes, I assumed a straight line on that specific condition, although I was more broadly trying to implement a more general solution.

      For your second comment, yes, you are absolutely right, calculating the slope would far easier, especially for a linear equation, and I would not even need to painfully consider whether the various calculated values are positive or negative. And even for a polynomial equation, say second or third degree, calculating the slope would narrow down faster on the solution (something similar to the Newton-Raphson method).

      My error was to initially think it could be done in 15 minutes and 20 lines of code, so I started to code something without carefully thinking of the problem, and discovered only when doing it that it was more complicated than I thought. If I have time this weekend, I'll try to come up with a better design.

      Je suis Charlie.
[reply]

        For a linear equation it could look like this (and yes, it took me more than 15 minutes...) 

        use strict;
use warnings;

my $equation = "(2*(4*x-8)+3*x)-(10*x+1-9)"; # " = 0" omitted
$equation =~ s/x/\$_[0]/g;
my $eval = sub { eval $equation };
my $val1 = $eval->(0);
my $val2 = $eval->(1);
die "No solution for this equation\n" unless $val1 - $val2;
my $result = -$val1 / ($val2 - $val1);

printf "Result is %.10f\n", $result;

        [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom