Skip to main content
gamedev.net
🔒 Locked

Does an algorithm like this exist?

Started by CTar 4 replies 1.3k views
Original Post
CTar
CTar
I want an algorithm which can predict all possible values of an integer expression. For instance if we have:
x = (f(4) + g(9) * 5 ) / 2
Where f(y)’s range is any integer x where (x-32)/y is an integer, and x is smaller than or equal to 32+8y. g(y)’s range is any integer x where (x-8)/y is an integer and x is smaller than or equal to 8+5y. So x should be one of the following: {36, 38, 40, 42, 44, 46, 48, 50, 52, 58, 60, 62, 64, 66, 68, 70, 72, 74, 81, 83, 85, 87, 89, 91, 93, 95, 97, 103, 105, 107, 109, 111, 113, 115, 117, 119, 126, 128, 130, 132, 134, 136, 138, 140, 142, 148, 150, 152, 154, 156, 158, 160, 162, 164} I have given it a little thought myself and think I can make it work with a reasonable performance. Before giving more thought to it I would like to know if any research have been made in this kinds of algorithms, so that I avoid re-inventing the wheel (my algorithm might even be worse than others out there). I have tried searching, but what is this kind of thing called? I tried various search terms, integer prediction, integer tracking, integer possibilities, etc. I have also tried some terms without integer in it.
Extrarius
Extrarius
You basically just need a computer algebraic system, which could translate the requirements for F(y) to:
F(y) = Q*y+32 where Q is any integer
F(y) <= 8*y+32
Then it could solve those to find that Q must be less than or equal to 8 and thus "F(y) = Q*Y+32" for some integer Q less than 9
Then it would translate G(z) into:
G(z) = R*z+8 for any integer R
G(z) <= 5*y+8
Thus "G(z) = R*z+8" for an integer R less than 6
And the main formula becomes
x = (Q*4+32 + 5*(R*9+8)) / 2
x = 2*Q + 20 + 22.5*R
at which point you just plug in the combinations of Q=0..8 and R=0..5

Basically you want a compiler and optimizer, and you'd do most of the manipulation while it's still in a tree format.
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
CTar
CTar
Thanks for the reply, I have thought about the approach you are using, but I'm finding it hard to believe that there aren't more efficient solutions. Well I'll try to experiment a little more with my own algorithm and see if I can beat the performance of a tree structure.
Sharlin
Sharlin
Constraint satisfaction problems

These kind of problems form a rather large subfield of Good Old-Fashioned AI. Usually, they are in principle easily reduced to search problems; the trick is doing the search fast enough, and representing the constraints appropriately.

[Edited by - Sharlin on July 11, 2006 3:11:51 PM]
Zahlman
Zahlman
"Diophantine equations", I think. :s
CTar
CTar
Diophantine equations seems to just be "indeterminate polynomial equation that only allows the variables to be integers" (from Wikipedia). I don't see how they will help me solve the problem, my equations has a finite set of solution. Also as far as I can see there is no way to restrict the values of certain variables. Would you like to expand on how you meant they could help solve the problem?

I have done some reading on CSP, it seems like a rather large subject so I will read some more about it before saying if it could be useful, but currently I can't see how it applies to determing the range of variables.

Thanks for your time.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.