Topic: ---={ Challenge }=--- Find inverse function

[ribarm]

Hi all...
Long time no challenges asked... This one is really tough and I think that IMHO is still impossible to be solved...
Now to get to the point. Through long period of time I coded in ALISP and very often I came into situation where I have to use math or some programming skills to write and translate real formula or pseudo code to ALISP defined function either by using (defun), (lambda) - defun-q I use rarely... Now if you take this simple formula A=B+3 and you translate it into this :

(defun a ( b )
  (+ b 3)
)

Result of (a 2) would be 5... That's fine... But what if formula is very complex and not so evident and you still have USUBR a which will operate the same (a 2) => 5... Now the goal of this challenge is to get USUBR ainv which will give (ainv 5) => 2 ...

So you have defined function - it could be as simple as (chr 65) => "A" ... Now we need to get (ascii) function from (chr), so that (chrinv "A") => 65 - the same as (ascii "A") => 65...

Let's see if some eminent person like Lee Mac, or MP can do it... For a start I am narrowing things to only pure math and math formula where you define function with 1 number argument and 1 return as number and the goal is to get inverse function also with 1 number argument and 1 return as number...

Thanks for reply in advance...
Regards, M.R.

[JohnK]

I posted a few routines called HOOK and LET many years ago that was related to this subject. -i.e. should be simple enough to build a function to construct functions.

Code - Auto/Visual Lisp: [Select]

1. (defun hook (name arg func)
2.   (eval (list 'defun name (list arg) func)))
3.  
4. (hook 'foo 'arg '(+ arg 3))
5. (hook 'fooinv 'arg '(- arg 3))

Code: [Select]

Command: (hook 'foo 'arg '(+ arg 3))
FOO

Command: (hook 'fooinv 'arg '(- arg 3))
FOOINV

Command: (foo 2)
5

Command: (fooinv 5)
2

[ribarm]

My simple solution considers involving global variables like *r*

Code - Auto/Visual Lisp: [Select]

1. (defun f ( a / b )
2.   (setq b (+ a a (/ a 2.0) (expt a 2))) ; place your formula with a
3.   (setq *r* (- b a))
4.   b
5. )
6.  
7. (defun finv ( b )
8.   (- b *r*)
9. )
10.  

But this is not what I was looking for in generalized terms... This is just math approach like I proposed in my finishing statement, but the problem is (chr 65) => "A" and (chrinv "A") => 65 in general

[VovKa]

My simple solution considers involving global variables like *r*

Code: [Select]

(f 2)
(finv 9)
(finv 26)
(f 4)


[ribarm]

My simple solution considers involving global variables like *r*

Code: [Select]

(f 2)
(finv 9)
(finv 26)
(f 4)


I don't get it... What do you want to say?

[JohnK]

I'm very confused by this thread.

[ribarm]

My simple solution considers involving global variables like *r*

Code: [Select]

(f 2)
(finv 9)
(finv 26)
(f 4)


I don't get it... What do you want to say?

I see the point... (finv) is not real inverse function of (f), but it's attempt to make connection between user defined function and return value... It works as inverse only if (f) is executed firstly and BTW. If (f) was never executed *r* would be nil and therefore and (finv) would break with error and fail...

[ribarm]

I'm very confused by this thread.

No, the topic is very useful if solution is to be found... It looks complicated, but in fact solution should be simple - someone should be able to create USUBR of already defined USUBR in the way that it operates reversed then it should... No need for formulas - just crack of foo to fooinv...

[VovKa]

I see the point...

yep
that's what i've meant

[VovKa]

Code: [Select]

(setq f_backup f)
(defun f (a) (setq *r* a) (f_backup a))
(defun f_inv () *r*)


[ribarm]

Here is another one based on *r*... Maybe this one is better...

Code - Auto/Visual Lisp: [Select]

1. (defun f ( a / b )
2.   (setq b (chr a)) ;; Place your formula with a here...
3.   (setq *r* (list b a))
4.   b
5. )
6.  
7. (defun finv ( b )
8.   (if (equal b (car *r*))
9.     (cadr *r*)
10.   )
11. )
12.  

Code: [Select]

(f 65) => "A"
(finv "A") => 65
(f 85) => "U"
(finv "U") => 85

Also (f) must be firstly initialized for (finv) to work as desired...

[Lee Mac]

This is impossible in general.

A simple example would be attempting to write an inverse hashing function.

[VovKa]

This is impossible in general.

i guess Marko just wants to know with what argument a function was called

[ribarm]

I was not referring to inverse function of complex function that is composed of other functions, just straight forward function with single formula and single argument and single return...

[ribarm]

This is impossible in general.

i guess Marko just wants to know with what argument a function was called

Not exactly... That among other things, but I really want inverse function of function...

[JohnK]

This is impossible in general.

i guess Marko just wants to know with what argument a function was called

As in: vl-bb-ref/set?

Not exactly... That among other things, but I really want inverse function of function...

Still very confusing!

[VovKa]

As in: vl-bb-ref/set?

it is also possible that Marko has a compiled lisp and wants to know what is happening inside it during the execution

[ribarm]

As in: vl-bb-ref/set?

it is also possible that Marko has a compiled lisp and wants to know what is happening inside it during the execution

No, I have no particular needs... I just want this solved as challenge and like I said I often use formulas inside LISPS and I wanted to know is there a way to reverse formula... Not to bang my head by using arithmetics and algebra I just guessed that there must be simple way through LISP defuns and by using PC (AutoCAD)...

[MP]

Not to bang my head by using arithmetics and algebra ...

If I understand what you're saying the arithmetics / algebra would instead be delegated to a non trivial, clever, auto heuristic function - authoring the adaptive arithmetics and algebra therein would dwarf the effort to write hundreds of specific 'inverse functions'.

tl;dr: While I salute the notion can't see it coming to fruition ... then again it's likely I don't understand the intent.

[ribarm]

With all respect to those that wrote inverse functions by using math or other techniques, I still can't imagine that with using PC there is no way to reverse operations of straight forward function... Simply if you have a=b+2, you have to write b=a-2... I imagine that for every input there is output in every formula... Isn't it true that every function with formula can be represented as curve in XY coordinate system... So can AutoCAD generate that curve and then just swap XY to YX and read that curve from YX as if it's function in XY (so formula is reversed)... Now outputs would become inputs and inputs outputs if we are to get values, but solution is just formula of that curve but in YX... In other words when you look it all just in XY, there is formula and curve and there should be formula for curve symetrical to function y=x... Shouldn't AutoCAD be capable of getting that curve function, or even there shouldn't even be need for getting formula - there is initial formula and corresponding Y^-1 (but no need for that - just normal Y function of curve is enough), so for every y coordinate there is x one read diractly from that curve...

[VovKa]

So can AutoCAD generate that curve and then just swap XY to YX and read that curve from YX as if it's function in XY (so formula is reversed)...

try it with a parabola

[ribarm]

With functions like (chr) - (ascii) the principle is the same just in list form built in initial function for ex. (chr)... For every number 65 there is "A" letter and opposite for every letter there is number - isn't that list already built-in (chr) function... So can list be reversed ((num letter) (65 "A") (85 "U") ...) and this is read as ((letter num) ("A" 65) ("U" 85) ...)... Basically we just need (defun invres ( chrlst ) (mapcar '(lambda ( x ) (list (cadr x) (car x))) chrlst))... (defun chrinv ( a ) (cadr (assoc a (invres chrlst))))

[MP]

try it with a parabola

That would be a pain in the latus rectum.

[Stefan]

Now outputs would become inputs and inputs outputs if we are to get values, but solution is just formula of that curve but in YX... In other words when you look it all just in XY, there is formula and curve and there should be formula for curve symetrical to function y=x... Shouldn't AutoCAD be capable of getting that curve function, or even there shouldn't even be need for getting formula - there is initial formula and corresponding Y^-1 (but no need for that - just normal Y function of curve is enough), so for every y coordinate there is x one read diractly from that curve...

It's only possible if the function is bijective, that means for each x there is only one y and vice-versa. Linear functions are like this.

So you know the f(x) function (not really the expression of the function, but only it's output) and you want to solve the x in y=f(x) .
Plot the function as spline with (x, f(x)) points and draw a horizontal Xline at (0,y,0). If you are lucky and it intersect the plot, the inverse is the x coordinate of the intersection.
Of course, the spline is finite, from a,f(a) to b,f(b). If it doesn't intersect, change the interval.

[Grrr1337]

So can AutoCAD generate that curve and then just swap XY to YX and read that curve from YX as if it's function in XY (so formula is reversed)...

try it with a parabola

Similar thought here, if the returns are exponentially growing or decaying, pseudocode -

Code - Auto/Visual Lisp: [Select]

1. (defun f ( a )
2.   (* 0.25 (+ 10 (* a a a) (* 2 (+ 5 a))))
3. )
4.  
5.  
6. _$ (mapcar 'f '(1 2 3 4 5 6 7 8 9 10)) ; observation
7. (5.75 8.0 13.25 23.0 38.75 62.0 94.25 137.0 191.75 260.0)
8.  
9. (defun fE ( a )
10.   ; replicate 'f as exponential
11.   ; ..
12. )
13.  
14. _$ (mapcar 'fE '(1 2 3 4 5 6 7 8 9 10)) ; observation and modify till reaching the results of 'f
15. (5.75 8.0 13.25 23.0 38.75 62.0 94.25 137.0 191.75 260.0)
16.  
17. (defun fEinv ( b )
18.   ; write out inverse exponential for 'fE
19. )
20.  
21. _$ (mapcar 'fEinv '(5.75 8.0 13.25 23.0 38.75 62.0 94.25 137.0 191.75 260.0))
22. '(1 2 3 4 5 6 7 8 9 10)

This might be of help.
But I don't think this approach would handle 'parabola jumps' - for special cases like: (if (< 5 a 10) (setq a 1)).

The ultimate would be machine-learning approach, collecting all of the data and acting from there with a tremendous amounf of if statements. 

EDIT: I mean if you want to inverse something that you don't know how its defined, the first step would be to attempt to replicate the definition and then come-up with a inversion.

[Grrr1337]

So you know the f(x) function (not really the expression of the function, but only it's output) and you want to solve the x in y=f(x) .
Plot the function as spline with (x, f(x)) points and draw a horizontal Xline at (0,y,0). If you are lucky and it intersect the plot, the inverse is the x coordinate of the intersection.
Of course, the spline is finite, from a,f(a) to b,f(b). If it doesn't intersect, change the interval.

Here is some initial code related to the above comment :

Code - Auto/Visual Lisp: [Select]

1. (defun f ( a )
2.   (* 0.25 (+ 10 (* a a a) (* 2 (+ 5 a))))
3. )
4.  
5. ;|
6. (f 4.5)
7. >> 30.0313 ; the result we're looking for
8. (fooInv f 4.5 '(1 2 3 4 5 6 7 8 9 10))
9. >> 29.6683
10. (fooInv f 4.5 '(1 2 3 4.3 4.8 5 6 7 8 9 10))
11. >> 29.9508
12. (fooInv f 4.5 '(1 2 3 4 4.5 5 6 7 8 9 10)) ; here the actual 'b' arg is suppled for running, hence (f b) is invoked and that makes 'fooInv' pointless
13. >> 30.0312 ; close enough
14. _$ (fooInv f 4.5 '(1 4.5 100))
15. >> 30.0313
16. |;
17. (defun fooInv ( f b args / L r )
18.   (cond
19.     ( (vl-some 'not (list f b args)) (prompt "\nInvalid arguments supplied.") )
20.     (
21.       (progn
22.         (and
23.           (not (vl-some (function (lambda (x) (equal b x 1e-4))) args))
24.           (prompt
25.             "\nThe argument 'b' is not contained within 'args',
26.            \nwhich may lead to not enough accurate result
27.            \nalthough that would make this sub useless."
28.           )
29.         ); and
30.         nil
31.       ); progn
32.     )
33.     ( (vl-catch-all-error-p (vl-catch-all-apply (function (lambda nil (setq L (mapcar '(lambda (x) (list x (f x) 0)) args))))))
34.       (prompt "\nThe supplied function 'f' errors out on some of the provided arguments.")
35.     )
36.     (
37.       (vl-catch-all-apply
38.         (function
39.           (lambda ( / spl xl )
40.             (and
41.               (setq spl (AddSpline L))
42.               (setq xl (AddXline (list (float b) 0.0 0.0)))
43.               (setq r (cadr (vlax-invoke spl 'InterSectWith xl acExtendNone)))
44.             )
45.             (mapcar 'vla-Delete (list spl xl))
46.           )
47.         )
48.       )
49.     )
50.   ); cond
51.   r
52. ); defun
53.  
54.  
55.  
56.  
57. (defun AddSpline ( 3DPtLst / r )
58.   (cond
59.     ( (not (vl-consp 3DPtLst)) )
60.     ( (not (vl-every 'vl-consp 3DPtLst)) )
61.     ( (progn (setq 3DPtLst (mapcar '(lambda (x) (if (= 2 (length x)) (append x '(0.0)) x)) 3DPtLst)) nil) )
62.     (
63.       (setq r
64.         (vla-AddSpline (vla-get-Block (vla-get-ActiveLayout (vla-get-ActiveDocument (vlax-get-acad-object))))
65.           (vlax-safearray-fill
66.             (vlax-make-safearray vlax-vbDouble (cons 0 (1- (length (apply 'append 3DPtLst)))))
67.             (apply 'append 3DPtLst)
68.           )
69.           (vlax-3d-point '(0. 0. 0.))
70.           (vlax-3d-point '(0. 0. 0.))
71.         )
72.       ); setq r
73.     )
74.   ); cond
75.   r
76. ); defun
77.  
78. ; (AddXline (getpoint))
79. (defun AddXline ( p )
80.   (vlax-invoke (vla-get-Block (vla-get-ActiveLayout (vla-get-ActiveDocument (vlax-get-acad-object))))  'AddXline
81.     p (mapcar '+ '(0.0 1.0 0.0) p)
82.   )
83. )

[JohnK]

With functions like (chr) - (ascii) the principle is the same just in list form built in initial function for ex. (chr)... For every number 65 there is "A" letter and opposite for every letter there is number - isn't that list already built-in (chr) function... So can list be reversed ((num letter) (65 "A") (85 "U") ...) and this is read as ((letter num) ("A" 65) ("U" 85) ...)...

> ("A" 65) ("U" 85)
That's an assocation list (or data structure). What's wrong with that? You don't need to reorder/reverse/clean/etc. the list at all; why would you?! The access to a list strucutre (via assoc, car, cdr, etc. is far, far faster then anything you could ever build). Frankly, people spend far too much time messing with lists; your functions should *NOT* care if the list is full of "nil" and/or "0's". And most times, your list doesn't need to be in ascending or alphabetical order; just let the built-in tools like ASSOC find them for you.

[ribarm]

@Grrr, very well coded... Thanks for your functions...
I actually modified it to represent fooInv like it should... (if you read my comment and Stefan's about inversion)

Code - Auto/Visual Lisp: [Select]

1. (defun f ( a )
2.   (* 0.25 (+ 10 (* a a a) (* 2 (+ 5 a))))
3. )
4.  
5. (defun _sin ( x / __sin k r ) ;; x - angle in radians
6.  
7.   (defun __sin ( x n / factorial )
8.  
9.     (defun factorial ( n )
10.       (if (/= (float n) 1.0) (* (float n) (factorial (1- n))) 1.0)
11.     )
12.  
13.     ((if (= (rem n 2) 0) + -) (/ (expt x (1+ (* 2 n))) (factorial (1+ (* 2 n)))))
14.   )
15.  
16.   (setq k 0 r 0.0)
17.   (while (<= (setq k (1+ k)) 200) ;; Tyler order - 200 expressions
18.     (setq r (+ r (__sin x k)))
19.   )
20.   (+ x r)
21. )
22.  
23. ;|
24. (f 1)
25. >> 5.75 ; minimal value of chosen interval
26. (f 4.5)
27. >> 30.0313 ; the result we're looking for
28. (f 10)
29. >> 260.0 ; maximal value of chosen interval
30. (fooInv f 30.0313) ; a=1, b=10, n=9 ['(1 2 3 4 5 6 7 8 9 10)]
31. >> 4.5231
32. (fooInv f 30.0313) ; a=1, b=10, n=18 ['(1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10)] ; here the actual 'b' arg is suppled for running, hence (f b) is invoked and that makes 'fooInv' near exact function
33. >> 4.5 ; exactly
34. (fooInv f 30.0313) ; a=1, b=8, n=2 ['(1 4.5 8)]
35. >> 4.50001 ; close enough
36.  
37. Using fooInv between min and max values of looking interval
38. (fooInv f 50.0) ; a=1, b=10, n=9 ['(1 2 3 4 5 6 7 8 9 10)]
39. >> 5.51922
40. (fooInv f 50.0) ; a=1, b=10, n=99
41. >> 5.52816 ; this result should be more accurate
42.  
43. Proof
44. (f 5.52816)
45. >> 50.0 ; exactly
46. |;
47.  
48. ;|
49. (_sin (/ pi 2.0))
50. >> 1.0
51. (rtos (/ pi 2.0) 2 20)
52. "1.570796326794896"
53. Interestingly I have this number from here : http://ronleigh.com/autolisp/ales15.htm
54. 3.1415926535897932385 / 2 = 1.57079632679489661925
55. (rtos (fooInv _sin 1.0) 2 20) ; a=1.570796326794891, b=1.570796326794901, n=10000
56. Command: (rtos (fooInv _sin 1.0) 2 20)
57. Specify minimal X value of looking interval : 1.570796326794891
58. Specify maximal X value of looking interval : 1.570796326794901
59. Specify segmentation of looking interval <100> : 10000
60. "1.570796326794900" - but there is probably mistake as 00 were repeating at the end (it looks like (rtos) rounded last 6 digit up to 10) :
61. Command: (rtos 1.57079632679489661925 2 20)
62. "1.570796326794896" from this output it looks that that isn't the case...
63. => PI = (rtos (* 2.0 1.570796326794900) 2 20) >> "3.141592653589800" - but there is probably mistake as 00 were repeating at the end
64. |;
65.  
66. (defun fooInv ( f b / args genargslst AddSpline AddLine L r )
67.  
68.   (vl-load-com)
69.  
70.   (defun genargslst ( / a b n dx k r )
71.     (setq a (getreal "\nSpecify minimal X value of looking interval : "))
72.     (setq b (getreal "\nSpecify maximal X value of looking interval : "))
73.     (initget 6)
74.     (setq n (getint "\nSpecify segmentation of looking interval <100> : "))
75.     (if (null n)
76.       (setq n 100)
77.     )
78.     (while (= n 1)
79.       (prompt "\nYou specified number 1 - that's not allowed...")
80.       (initget 6)
81.       (setq n (getint "\nSpecify segmentation of looking interval <100> : "))
82.       (if (null n)
83.         (setq n 100)
84.       )
85.     )
86.     (setq dx (/ (- b a) (float n)))
87.     (setq k -1)
88.     (repeat (1+ n)
89.       (setq r (cons (+ a (* dx (setq k (1+ k)))) r))
90.     )
91.     (reverse r)
92.   )
93.  
94.   (defun AddSpline ( 3DPtLst / r )
95.     (cond
96.       ( (not (vl-consp 3DPtLst)) )
97.       ( (not (vl-every 'vl-consp 3DPtLst)) )
98.       ( (progn (setq 3DPtLst (mapcar '(lambda ( x ) (if (= 2 (length x)) (append x '(0.0)) x)) 3DPtLst)) nil) )
99.       (
100.         (setq r
101.           (vla-AddSpline (vla-get-Block (vla-get-ActiveLayout (vla-get-ActiveDocument (vlax-get-acad-object))))
102.             (vlax-safearray-fill
103.               (vlax-make-safearray vlax-vbDouble (cons 0 (1- (length (apply 'append 3DPtLst)))))
104.               (apply 'append 3DPtLst)
105.             )
106.             (vlax-3d-point '(0. 0. 0.))
107.             (vlax-3d-point '(0. 0. 0.))
108.           )
109.         ); setq r
110.       )
111.     ); cond
112.     r
113.   ); defun
114.    
115.   (defun AddLine ( p1 p2 )
116.     (vlax-invoke (vla-get-Block (vla-get-ActiveLayout (vla-get-ActiveDocument (vlax-get-acad-object)))) 'AddLine
117.       p1 p2
118.     )
119.   )
120.  
121.   (setq args (genargslst))
122.   (cond
123.     ( (vl-some 'not (list f b args)) (prompt "\nInvalid arguments supplied.") )
124.     (
125.       (progn
126.         (and
127.           (not (vl-some (function (lambda ( x ) (equal b (f x) 1e-2))) args))
128.           (prompt
129.             "\nThe argument 'b' is not contained within f(x),
130.             \nwhich may lead to not enough accurate result
131.             \nalthough that would make this sub useless.
132.             \n"
133.           )
134.         ); and
135.         nil
136.       ); progn
137.     )
138.     ( (vl-catch-all-error-p (vl-catch-all-apply (function (lambda nil (setq L (mapcar '(lambda ( x ) (list x (f x) 0)) args))))))
139.       (prompt "\nThe supplied function 'f' errors out on some of the provided arguments.")
140.     )
141.     (
142.       (vl-catch-all-apply
143.         (function
144.           (lambda ( / spl li )
145.             (and
146.               (setq spl (AddSpline L))
147.               (setq li (AddLine (list (car args) (float b) 0.0) (list (last args) (float b) 0.0)))
148.               (setq r (car (vlax-invoke spl 'InterSectWith li acExtendNone)))
149.             )
150.             (mapcar 'vla-Delete (list spl li))
151.           )
152.         )
153.       )
154.     )
155.   ); cond
156.   r
157. ); defun
158.  

[ribarm]

As you can see, I tried to get lastly digits of number PI by using custom (_sin) function based on Tyler order and this method - inverse function - that would be arcsin... But unfortunately there is probably some mistake - look into comments of my code I posted in previous reply...

[EDIT : Probably (rtos) rounded last digit which is initially 6 to up 10, so that result is correct, but not what I wanted...]

[EDIT : It seems that (rtos) is fine : (rtos 1.57079632679489661925 2 20) => "1.570796326794896"]

[jtoverka]

So you have defined function - it could be as simple as (chr 65) => "A" ... Now we need to get (ascii) function from (chr), so that (chrinv "A") => 65 - the same as (ascii "A") => 65...

How complex are you willing to go? A two variable function can yield the same result with multiple inputs.