LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 01-27-2019, 01:57 AM   #76
pan64
LQ Addict
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 21,691

Rep: Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274

Quote:
Originally Posted by dogpatch View Post
pass or fail equations for my attempt to correct for floating point inaccuracies by rounding. Still haven't devised an acceptable solution, but am working on it. Any tips would be welcome.
You will never find a solution. There is no way (at least I don't know any) to decide if that was a limitation of hardware/software or it is just "almost" an integer. For example: 9^(-210) is not equal to 0, but ....
I'm afraid you need to analyze/evaluate the expression (=not calculate the result) and find out if the result was an integer or not. And that is a really hard task.

Last edited by pan64; 01-27-2019 at 02:01 AM.
 
1 members found this post helpful.
Old 01-27-2019, 06:03 PM   #77
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 490
Blog Entries: 4

Rep: Reputation: 238Reputation: 238Reputation: 238
Quote:
Originally Posted by pan64 View Post
You will never find a solution. There is no way (at least I don't know any) to decide if that was a limitation of hardware/software or it is just "almost" an integer. For example: 9^(-210) is not equal to 0, but ....
I disagree. See my online calculator. It employs reverse polish notation. So, to calculate 9 to the -210 power, enter 9, then the 'Enter' button, then 210 then -x, then y**x. With its current precision setting, my page will not do the calculation, but it will return an error rather than give a false answer, and that's what i'm trying to achieve, to avoid the false equations.

Am currently working on including this same logic into my LQ 2019 challenge page. Please beware that i may have to do much of the testing on the live page, so don't be surprised at some seg faults or other bugs. Will try to report back when (if) i have it working as i hope. As i type this, it is performing at the same level as before (with possible rounding errors).
 
Old 01-28-2019, 01:05 AM   #78
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Original Poster
Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by astrogeek View Post
I have not yet tried to use your latest code, but am not clear from the discussion whether the expression ranking produces different results sets...?
The ranking is in the filtering stage, so yes, the output is different. However, it doesn't make any difference in the generation of expressions. For that, I still go through all permutations of digits, operations, and order of operations, typically generating thousands of expressions, many of which look crazy. Then the filters pick out the ones that best fit the user's preferences.

Quote:
And the same for your fractional math, did it produce any notably different results sets, or mostly increase the confidence level? Sorry in advance if you have answered those and I have missed it.
I actually didn't look closely at that... until today (since you asked). Surprisingly it does not make a huge difference. I searched all 4-digit years and found only a few in which fractional math obtains a whole number that was missed by floating-point math. Here is the complete list:
Code:
year      equation
----    ------------
1358    31 = 8^(5/3)-1
1789    28 = 8/(9/7-1)
2778    58 = 7*(8+2/7)
2779    61 = 7*(9-2/7)
3388    24 = 8/(3-8/3)
3588    40 = 8^(5/3)+8
3589    41 = 8^(5/3)+9
3778    29 = 7*(3+8/7)
5689    20 = 5*8^(6/9)
5778    61 = 7*(8+5/7)
7779    58 = 7*(7+9/7)
Fractional math didn't miss any that were found by floating-point math.

Note: I have done this in a Python which identifies itself as "Python 3.2.3 (default, Mar 25 2017, 10:08:27) [GCC 4.7.2] on linux2." The truncation errors are different in C, and possibly even in different Pythons, so different numbers might be missed.

Last edited by Beryllos; 01-28-2019 at 01:21 AM. Reason: added the Version ID of the python I used
 
1 members found this post helpful.
Old 01-28-2019, 01:05 AM   #79
pan64
LQ Addict
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 21,691

Rep: Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274Reputation: 7274
I'm really sorry, but you don't understand. You cannot check the limitations of the software/hardware by this way. You may use different software but there will be always some expressions where you cannot decide if rounding is acceptable or not. The only way to know is if you analyze that expression.
This is all about the "LSB" (least significant bit) and the forced rounding because there are no more bits.
 
1 members found this post helpful.
Old 01-28-2019, 01:32 AM   #80
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Original Poster
Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
In fractional math there is no rounding and no truncation. Everything is stored as 2 integers: numerator and denominator. All math operations of {+, -, *, /, ^} take 2 fraction arguments and yield an exact fraction result, and results are reduced to the lowest terms (numerator and denominator having no common factors). To determine whether a result is a whole number, one needs only to inspect the denominator. If the denominator is 1, the fraction is a whole number, and the whole number is the numerator.

Last edited by Beryllos; 01-28-2019 at 01:41 AM. Reason: clarify which math operations may be exactly computed
 
Old 01-28-2019, 01:52 AM   #81
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Original Poster
Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Correction: The power function (^) with fractions does not always result in an exact fraction. However it is possible to determine with certainty when the result is an exact fraction.

In my fraction-based programs, all non-fraction results of the power function are treated as errors and are rejected. Unfortunately this causes some exact expressions to be rejected, for example, 2=(2^(1/2))^2.

Last edited by Beryllos; 01-28-2019 at 01:55 AM.
 
1 members found this post helpful.
Old 01-28-2019, 02:29 AM   #82
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1}
Posts: 6,258
Blog Entries: 24

Rep: Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193
Quote:
Originally Posted by Beryllos View Post
I actually didn't look closely at that... until today (since you asked). Surprisingly it does not make a huge difference. I searched all 4-digit years and found only a few in which fractional math obtains a whole number that was missed by floating-point math. Here is the complete list:
Code:
year      equation
----    ------------
1358    31 = 8^(5/3)-1
1789    28 = 8/(9/7-1)
2778    58 = 7*(8+2/7)
2779    61 = 7*(9-2/7)
3388    24 = 8/(3-8/3)
3588    40 = 8^(5/3)+8
3589    41 = 8^(5/3)+9
3778    29 = 7*(3+8/7)
5689    20 = 5*8^(6/9)
5778    61 = 7*(8+5/7)
7779    58 = 7*(7+9/7)
Fractional math didn't miss any that were found by floating-point math.
Thanks for taking the trouble to look at that, and for the list of examples you found.

My curiosity was due mostly to the last changes I made to my own code before I was interrupted the past week or so, and the initial resuts it produced. Until then I had been simply evaluating my set of expressions without any real validation of the results, relying on the C language for accuracy and error reporting. So I had at least added a check of the final results for overflow/underflow with fpclassify macros, but after running a few hundred years through it I found only one expression which produced an error, which was surprising as I expected many more. And in truth, it should not have passed my eyeball filter for evaluation anyway (it was a high negative power of 9 which could not produce a useful result in any event).

But I have not been able to test or play more and have been wondering if your own results produced any great difference. Now I know!

I have had opportunity to work with my code a few hours today and have greatly improved my own methods. I had been simply writing the expressions inline for evaluation, as args to a function which validated them and produced the formatted output. That was a quick and dirty way for testing my expression sets initially, but was a bit cumbersome to extend and modify once I had more than a few dozen expressions!

So today I wrote a simple parser which accepts those expressions in symbolic form, like 'a*(b-c)/d', along with the array of permuted digits, a,b,c and d, and an optional limit condition and generates an AST which it then evluates for the result. The limit condition is a boolean which prevents runtime evaluation of an expression under conditions which would obviously fail, but evaluate it otherwise.

For example, my calling convention is now...

Code:
solve('a*(b-c)/d', digits, d==0);
solve('(a+b)^(c-d)', digits, (c-d)<0);
... where digits is array of permuted digits, a,b,c, and d values, and the third arg is the limit, if it evaluates true at runtime the expression is not evaluated.

This also gives me the option to show which expression produced a given result both symbolically and with the numeric substitutions, which is very helpful! Evaluation of the AST allows for better error checking, and validation of intermediate results. I only got it working this evening but it should be nice once I get it fully set up.

I have run your v6 version and compared a few results which look very good, but need to clean up my spaghetti and bury all the dead ends before posting code or results... more fun for the morrow!

My compliments on your code by the way! My python proficiency is abyssmal, but I have been able to work through most of it, at least at a superficial level. Very nicely done!

Last edited by astrogeek; 01-28-2019 at 03:47 AM. Reason: comment, typos, clarity
 
1 members found this post helpful.
Old 01-28-2019, 02:56 AM   #83
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1}
Posts: 6,258
Blog Entries: 24

Rep: Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193
Quote:
Originally Posted by pan64 View Post
I'm really sorry, but you don't understand. You cannot check the limitations of the software/hardware by this way. You may use different software but there will be always some expressions where you cannot decide if rounding is acceptable or not. The only way to know is if you analyze that expression.
This is all about the "LSB" (least significant bit) and the forced rounding because there are no more bits.
I agree (but with some lack of understanding of Beryllos' fractional math). As noted before, you can make the error as small as you like, but you cannot make it zero. Adding new results by narrowing the error band around integer values does not make those numbers integers, it simply refines your definition of what you are willing to accept, and you cannot reach any ultimate end in that direction.

With integer math the representation of numbers is exact, unlike floating point representations. But even so, the result of rational integer expressions is not exactly representable, so I do not see how that can be avoided - some numbers simply cannot be represented exactly - the LSB limit as you say.

The only way around that is to analyze the expressions themselves, which is a central part of the path my own solution has attempted to follow. Stay away from the edge cases and be happy!

That said, I have had to refresh my rusty grasp of the fine points of floating point math on computers just to follow the conversation, and that has been a very good thing for me!

Last edited by astrogeek; 01-28-2019 at 03:06 AM. Reason: typos, added comments
 
1 members found this post helpful.
Old 01-28-2019, 09:55 AM   #84
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Original Poster
Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by pan64 View Post
This is all about the "LSB" (least significant bit) and the forced rounding because there are no more bits.
I think we agree that if you start with a bunch of integers, you can add, subtract, and multiply them without truncation/rounding error. The difficulty starts with division.

Okay, here is a crazy suggestion: Can we structure the problem so that division is accomplished without actually dividing? Yes, we can. You have probably done it on paper, and we can do it in software, by fraction structures (or objects) and methods.

Example 28=8/(9/7-1)...
As pdf with equations:
fraction-example.pdf

As Python:
Code:
$ python3
Python 3.2.3 (default, Mar 25 2017, 10:08:27) 
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import fractions
>>> a=fractions.Fraction(8)
>>> b=fractions.Fraction(9)
>>> c=fractions.Fraction(7)
>>> d=fractions.Fraction(1)
>>> a
Fraction(8, 1)
>>> b
Fraction(9, 1)
>>> c
Fraction(7, 1)
>>> d
Fraction(1, 1)
>>> b/c
Fraction(9, 7)
>>> b/c-d
Fraction(2, 7)
>>> a/(b/c-d)
Fraction(28, 1)
>>> (a/(b/c-d)).denominator
1
>>> (a/(b/c-d)).numerator
28
Fractional powers are more problematic but partially solvable. Imagine how you would find the 1/3 power of 125 with a 4-function calculator. You could search for an integer solution by trying the 3rd power of integers:
Code:
0^3 = 0
1^3 = 1
2^3 = 8
3^3 = 27
4^3 = 64
5^3 = 125
The last result tells us that 125^(1/3) = 5.

If no integer solution exists, we know as soon as the trial grows larger than the target. For example, searching for the 1/3 power of 50:
Code:
0^3 = 0
1^3 = 1
2^3 = 8
3^3 = 27
4^3 = 64
No result is equal to 50. The last result is larger than 50. That tells us there is no integer solution.

The Python fractions module does not do it this way. For non-integer powers, it converts to double, calculates the answer as double, and leaves it at that:
Code:
>>> e=fractions.Fraction(125)
>>> f=fractions.Fraction(1,3)
>>> e
Fraction(125, 1)
>>> f
Fraction(1, 3)
>>> e**f
4.999999999999999
Therefore, for this project, I wrote my own routine for fractional powers of fractions, based on the above integer method.

Last edited by Beryllos; 01-28-2019 at 10:06 AM. Reason: Corrected last Python code block (originally didn't use fractions module)
 
2 members found this post helpful.
Old 01-28-2019, 10:16 AM   #85
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Original Poster
Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
I figured someone must have done this in C as well. With a short search, I found this introductory web page on fraction arithmetic using structures in C:

http://www.cs.utsa.edu/~wagner/CS207...fractions.html

It does the four basic functions, but not powers.

Last edited by Beryllos; 01-28-2019 at 10:30 AM. Reason: corrected last sentence describing web article
 
2 members found this post helpful.
Old 01-28-2019, 01:33 PM   #86
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1}
Posts: 6,258
Blog Entries: 24

Rep: Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193Reputation: 4193
Quote:
Originally Posted by Beryllos View Post
I think we agree that if you start with a bunch of integers, you can add, subtract, and multiply them without truncation/rounding error. The difficulty starts with division.

Okay, here is a crazy suggestion: Can we structure the problem so that division is accomplished without actually dividing? Yes, we can. You have probably done it on paper, and we can do it in software, by fraction structures (or objects) and methods.

Example 28=8/(9/7-1)...
As pdf with equations:
Attachment 29617
Thanks for your patience and persistence explaining this very simple idea. I think my bias against taking time to try to understand the python fraction library blocked my ability to see the simple point of the math. Doh!

So the method is really a way of evaluating an integer expression which tells you whether the result is an integer or not, and produces the integer result in the process. The problem of reducing the denominator does not introduce errors because done with integers you only care if there is a remainder, not what that remainder is. Elegant simplicity, take a bow!

The fact that there remain cases which it cannot handle is still a limitation of the binary representation, but the method allows you to divide the expressions into classes with and without those potential errors - restricting the error band in a different sense.

So this goes in the "right" direction, evaluating the expressions, as opposed to testing the numeric accuracy of the result.

Last edited by astrogeek; 01-28-2019 at 02:02 PM. Reason: Added comment
 
2 members found this post helpful.
Old 01-29-2019, 08:53 PM   #87
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 490
Blog Entries: 4

Rep: Reputation: 238Reputation: 238Reputation: 238
Quote:
Originally Posted by Beryllos View Post
I figured someone must have done this in C as well. With a short search, I found this introductory web page on fraction arithmetic using structures in C:

http://www.cs.utsa.edu/~wagner/CS207...fractions.html

It does the four basic functions, but not powers.
I've never before been acquainted with fraction arithmetic. This page and your work gives me the tip i was looking for. Am looking into fraction math, and may even put my arbitrary precision logic on hold while i do so. Thank you, Beryllos.
 
Old 01-30-2019, 08:02 AM   #88
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 490
Blog Entries: 4

Rep: Reputation: 238Reputation: 238Reputation: 238
Quote:
Originally Posted by Beryllos View Post
Correction: The power function (^) with fractions does not always result in an exact fraction. However it is possible to determine with certainty when the result is an exact fraction.

In my fraction-based programs, all non-fraction results of the power function are treated as errors and are rejected. Unfortunately this causes some exact expressions to be rejected, for example, 2=(2^(1/2))^2.
Have been playing with fractional arithmetic, and am experimenting with your idea of including the power operation. My C structure currently looks like this:
Code:
struct frac
    {
    long num;
    long den;
    };
struct b_x
    {
    long base;
    struct frac exp;
    };
struct f_x
    {
    struct b_x fnum;
    struct b_x fden;
    };
which allows me to use your technique of including exponents, even fractional ones.

Usiing your example, the resulting structure end up like this
Code:
(2^(2/2) / (1^(1/1)
which evaluates quite easily to 2, using pure integer math.

Have also processed this expression
Code:
8^(5/3)
as
Code:
(8^(5/3) / (1^(1/1)
which evaulates to 32.

I think i get into trouble if the main denominator is anything but 1^(1/1), that is, i cannot evaluate fractional exponents of fractions.
 
2 members found this post helpful.
Old 01-30-2019, 08:02 AM   #89
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 490
Blog Entries: 4

Rep: Reputation: 238Reputation: 238Reputation: 238
Quote:
Originally Posted by Beryllos View Post
Correction: The power function (^) with fractions does not always result in an exact fraction. However it is possible to determine with certainty when the result is an exact fraction.

In my fraction-based programs, all non-fraction results of the power function are treated as errors and are rejected. Unfortunately this causes some exact expressions to be rejected, for example, 2=(2^(1/2))^2.
Have been playing with fractional arithmetic, and am experimenting with your idea of including the power operation. My C structure currently looks like this:
Code:
struct frac
    {
    long num;
    long den;
    };
struct b_x
    {
    long base;
    struct frac exp;
    };
struct f_x
    {
    struct b_x fnum;
    struct b_x fden;
    };
which allows me to use your technique of including exponents, even fractional ones.

Usiing your example, the resulting structure end up like this
Code:
(2^(2/2) / (1^(1/1)
which evaluates quite easily to 2, using pure integer math.

Have also processed this expression
Code:
8^(5/3)
as
Code:
(8^(5/3) / (1^(1/1)
which evaulates to 32.

I think i get into trouble if the main denominator is anything but 1^(1/1), that is, i cannot evaluate fractional exponents of fractions.
 
2 members found this post helpful.
Old 01-30-2019, 08:09 AM   #90
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 490
Blog Entries: 4

Rep: Reputation: 238Reputation: 238Reputation: 238
I should add that in the above two examples, the evaulation process is slightly different. In the first case, it simply recognizes that the fractional exponent is not really fractional. In the second case, it evaluates 8^(1/3) using your trial and error method of looking for integer roots.

In no case would this technique work for non-integer roots.
 
2 members found this post helpful.
Old 01-30-2019, 01:00 PM   #91
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Original Poster
Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319

Quote:
Originally Posted by dogpatch View Post
Have been playing with fractional arithmetic, and am experimenting with your idea of including the power operation. My C structure currently looks like this:

[code block]

which allows me to use your technique of including exponents, even fractional ones.

Using your example, the resulting structure end up like this

[examples] Looking good!

I think i get into trouble if the main denominator is anything but 1^(1/1), that is, i cannot evaluate fractional exponents of fractions.
Great progress so far! Well done!

We don't need a new and larger structure for the problem as I've approached it so far. You can continue to store all the variables as fractions. When we come to a power operation, we have a fraction raised to the power of a fraction, and we want the result to be a fraction (or if it's not, we throw away the entire expression and move on the the next).

I solve that power function by breaking both fractional arguments into numerators and denominators (integers all), carrying out 4 separate power operations, and then repackaging it as a fraction at the end, assuming solutions are found.

I know you are on the right track, because you got the right answer for 8^(5/3)=32.

In any case, I wrote up some equations to explain how I developed my fractional power algorithm:
fractional power algorithm.pdf

By the way, I make these kinds of documents in Libre Office Writer using its formula editor. It's a bit of a pain to get all the fraction bars and parentheses in the right places, but it works.

Last edited by Beryllos; 01-30-2019 at 01:01 PM.
 
1 members found this post helpful.
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
LXer: Minilens – Fun Open Source Puzzle Platform Game LXer Syndicated Linux News 0 10-27-2017 11:54 AM
LXer: SpaceChem, One of the Best Indie Puzzle Game Released this Year for Linux LXer Syndicated Linux News 0 06-19-2011 03:50 PM
Puzzle Challenge: Collecting lots of files from many people? General General 6 06-25-2010 06:35 AM
<fun> The Windows Crash </fun> Simon Bridge General 6 08-26-2007 07:46 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 12:27 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration