Topic: -={ Challenge }=- Addition without Arithmetic Operators

[ribarm]

_+VK1 is correct, but :

Code: [Select]

Command: (fix 3e+9)
3.0e+009

Command: (type 3e+9)
REAL

Command: (type (fix 3e+9))
REAL


[Lee Mac]

A little test:

Code: [Select]

(setq n1 1000000000 n2 2000000000)

3,000,000,000 > 2,147,483,647

[Marc'Antonio Alessi]

A little test:

Code: [Select]

(setq n1 1000000000 n2 2000000000)

3,000,000,000 > 2,147,483,647

I just wanted to point out that some functions do not have the same behavior of the operator "+" that they are replacing.

About performance (test not exhaustive), maybe _+STF2?...

Code: [Select]

(defun c:+test ( / n1 n2)
(setq n1 1 n2 2)
(repeat 9
(princ "\nn1= ")(princ n1)(princ "  n2= ")(princ n2)(princ "\n")
(Benchmark '(
(_+Ale2  n1 n2)
(_+Lee1  n1 n2)
(_+Lee5  n1 n2)
(_+Stf2  n1 n2)
(_+Rib1  n1 n2)
)           )
(setq n1 (* 10 n1) n2 (* 10 n2))
))
(c:+test)
(princ)

Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
n1= 1  n2= 2
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+STF2 N1 N2).....1763 / 1.53 <fastest>
    (_+LEE5 N1 N2).....1794 / 1.5
    (_+RIB1 N1 N2).....1810 / 1.49
    (_+ALE2 N1 N2).....2106 / 1.28
    (_+LEE2 N1 N2).....2590 / 1.04
    (_+LEE1 N1 N2).....2699 / 1 <slowest>

n1= 10  n2= 20
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+LEE1 N1 N2).....1747 / 2.02 <fastest>
    (_+STF2 N1 N2).....1763 / 2
    (_+LEE5 N1 N2).....1810 / 1.95
    (_+RIB1 N1 N2).....2278 / 1.55
    (_+ALE2 N1 N2).....2854 / 1.24
    (_+LEE2 N1 N2).....3526 / 1 <slowest>

n1= 100  n2= 200
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+LEE1 N1 N2).....1731 / 4.41 <fastest>
    (_+STF2 N1 N2).....1778 / 4.29
    (_+LEE5 N1 N2).....1810 / 4.21
    (_+RIB1 N1 N2).....1810 / 4.21
    (_+ALE2 N1 N2).....2824 / 2.7
    (_+LEE2 N1 N2).....7629 / 1 <slowest>

n1= 1000  n2= 2000
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+LEE1 N1 N2).....1747 / 4.17 <fastest>
    (_+RIB1 N1 N2).....1809 / 4.03
    (_+STF2 N1 N2).....1888 / 3.86
    (_+ALE2 N1 N2).....2121 / 3.43
    (_+LEE5 N1 N2).....3213 / 2.27
    (_+LEE2 N1 N2).....7285 / 1 <slowest>

n1= 10000  n2= 20000
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+STF2 N1 N2).....1763 / 4.88 <fastest>
    (_+RIB1 N1 N2).....1825 / 4.71
    (_+LEE5 N1 N2).....2169 / 3.96
    (_+LEE1 N1 N2).....2262 / 3.8
    (_+ALE2 N1 N2).....2855 / 3.01
    (_+LEE2 N1 N2).....8595 / 1 <slowest>

n1= 100000  n2= 200000
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+STF2 N1 N2)......1747 / 7.25 <fastest>
    (_+LEE1 N1 N2)......1779 / 7.12
    (_+RIB1 N1 N2)......1794 / 7.06
    (_+LEE5 N1 N2)......2184 / 5.8
    (_+ALE2 N1 N2)......3011 / 4.21
    (_+LEE2 N1 N2).....12667 / 1 <slowest>

n1= 1000000  n2= 2000000
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+STF2 N1 N2)......1747 / 7.05 <fastest>
    (_+LEE5 N1 N2)......1809 / 6.8
    (_+RIB1 N1 N2)......1810 / 6.8
    (_+LEE1 N1 N2)......1888 / 6.52
    (_+ALE2 N1 N2)......2121 / 5.8
    (_+LEE2 N1 N2).....12308 / 1 <slowest>

n1= 10000000  n2= 20000000
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+LEE1 N1 N2)......1731 / 6.36 <fastest>
    (_+STF2 N1 N2)......1748 / 6.3
    (_+LEE5 N1 N2)......1809 / 6.09
    (_+RIB1 N1 N2)......2698 / 4.08
    (_+ALE2 N1 N2)......2792 / 3.94
    (_+LEE2 N1 N2).....11014 / 1 <slowest>

n1= 100000000  n2= 200000000
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+LEE1 N1 N2)......1732 / 7.43 <fastest>
    (_+STF2 N1 N2)......1747 / 7.37
    (_+LEE5 N1 N2)......1809 / 7.11
    (_+RIB1 N1 N2)......1826 / 7.05
    (_+ALE2 N1 N2)......2168 / 5.94
    (_+LEE2 N1 N2).....12870 / 1 <slowest>


Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
n1= 1  n2= 2
Elapsed milliseconds / relative speed for 65536 iteration(s):
    (_+LEE1 N1 N2).....2075 / 1.27 <fastest>
    (_+LEE5 N1 N2).....2246 / 1.17
    (_+STF2 N1 N2).....2246 / 1.17
    (_+RIB1 N1 N2).....2246 / 1.17
    (_+ALE2 N1 N2).....2636 / 1 <slowest>

n1= 10  n2= 20
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+STF2 N1 N2).....1107 / 1.25 <fastest>
    (_+RIB1 N1 N2).....1155 / 1.2
    (_+LEE5 N1 N2).....1170 / 1.19
    (_+LEE1 N1 N2).....1249 / 1.11
    (_+ALE2 N1 N2).....1389 / 1 <slowest>

n1= 100  n2= 200
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+STF2 N1 N2).....1123 / 1.32 <fastest>
    (_+RIB1 N1 N2).....1154 / 1.28
    (_+LEE5 N1 N2).....1170 / 1.27
    (_+LEE1 N1 N2).....1326 / 1.12
    (_+ALE2 N1 N2).....1482 / 1 <slowest>

n1= 1000  n2= 2000
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+LEE1 N1 N2).....1076 / 1.33 <fastest>
    (_+LEE5 N1 N2).....1123 / 1.28
    (_+STF2 N1 N2).....1139 / 1.26
    (_+RIB1 N1 N2).....1139 / 1.26
    (_+ALE2 N1 N2).....1435 / 1 <slowest>

n1= 10000  n2= 20000
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+LEE1 N1 N2).....1061 / 1.32 <fastest>
    (_+LEE5 N1 N2).....1123 / 1.25
    (_+RIB1 N1 N2).....1124 / 1.25
    (_+STF2 N1 N2).....1170 / 1.2
    (_+ALE2 N1 N2).....1404 / 1 <slowest>

n1= 100000  n2= 200000
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+LEE1 N1 N2).....1092 / 1.32 <fastest>
    (_+RIB1 N1 N2).....1279 / 1.12
    (_+LEE5 N1 N2).....1357 / 1.06
    (_+STF2 N1 N2).....1419 / 1.01
    (_+ALE2 N1 N2).....1436 / 1 <slowest>

n1= 1000000  n2= 2000000
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+STF2 N1 N2).....1108 / 1.24 <fastest>
    (_+LEE1 N1 N2).....1139 / 1.21
    (_+LEE5 N1 N2).....1139 / 1.21
    (_+RIB1 N1 N2).....1170 / 1.17
    (_+ALE2 N1 N2).....1373 / 1 <slowest>

n1= 10000000  n2= 20000000
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+STF2 N1 N2).....1092 / 1.26 <fastest>
    (_+LEE5 N1 N2).....1155 / 1.19
    (_+LEE1 N1 N2).....1170 / 1.17
    (_+RIB1 N1 N2).....1201 / 1.14
    (_+ALE2 N1 N2).....1372 / 1 <slowest>

n1= 100000000  n2= 200000000
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (_+STF2 N1 N2).....1092 / 1.11 <fastest>
    (_+LEE5 N1 N2).....1139 / 1.07
    (_+LEE1 N1 N2).....1154 / 1.05
    (_+RIB1 N1 N2).....1170 / 1.04
    (_+ALE2 N1 N2).....1217 / 1 <slowest>


[Stefan]

Marc,

My second function STF2 fails if b is not a multiple of a, because of (/ b a).

Code: [Select]

(stf2 2 5) -> 6
This one is correct, but not so concise

Code - Auto/Visual Lisp: [Select]

1. (defun _+Stf3 (a b)
2.   (cond
3.     ((zerop a) b)
4.     ((and (= (type a) 'int)
5.           (= (type b) 'int)
6.           )
7.      (fix (* a (1+ (/ b 1. a))))
8.      )
9.      ((* a (1+ (/ b a))))
10.     )
11.   )

Or this one, for integers only

Code - Auto/Visual Lisp: [Select]

1. (defun _+Stf4 (a b)
2.   (if (zerop a) b (fix (* a (1+ (/ b 1. a)))))
3.   )

[Marc'Antonio Alessi]

_+VK1 is correct, but :

Code: [Select]

Command: (fix 3e+9) 3.0e+009
Command: (type 3e+9) REAL
Command: (type (fix 3e+9)) REAL


you are right, about test  _+VK1 is in medium position.

Code: [Select]

n1= 10000000  n2= 20000000
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+LEE1 N1 N2).....1997 / 1.05 <fastest>
    (_+STF2 N1 N2).....2029 / 1.03
    (_+VK1 N1 N2)......2059 / 1.02
    (_+LEE5 N1 N2).....2074 / 1.01
    (_+RIB1 N1 N2).....2091 / 1 <slowest>

n1= 100000000  n2= 200000000
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+STF2 N1 N2).....2028 / 1.06 <fastest>
    (_+VK1 N1 N2)......2091 / 1.03
    (_+RIB1 N1 N2).....2091 / 1.03
    (_+LEE5 N1 N2).....2106 / 1.02
    (_+LEE1 N1 N2).....2153 / 1 <slowest>

[ribarm]

Also one note... My function isn't adequate for large integers... I've complicated unnecessary with (cond)... It should be just :

Code - Auto/Visual Lisp: [Select]

1. (defun _+ ( a b )
2.   (if (< (abs a) (abs b))
3.     (- (* 2 a) (- a b))
4.     (- (* 2 b) (- b a))
5.   )
6. )
7.  

Regards...

[Marc'Antonio Alessi]

new one:

Code: [Select]

(defun _+Ale3 (a b)
      (or _+ (setq _+ (eval (read (chr 43)))))
      (_+ a b)
)new test:

Code: [Select]

Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved


n1= 1  n2= 2
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+ALE3 N1 N2).....1810 / 2.05 <fastest>
    (_+LEE5 N1 N2).....1918 / 1.94
    (_+STF3 N1 N2).....2044 / 1.82
    (_+STF4 N1 N2).....2496 / 1.49
    (_+LEE1 N1 N2).....2886 / 1.29
    (_+RIB2 N1 N2).....3027 / 1.23
    (_+VK1 N1 N2)......3713 / 1 <slowest>

n1= 20  n2= 40
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+STF4 N1 N2).....1685 / 2.34 <fastest>
    (_+LEE1 N1 N2).....1919 / 2.06
    (_+VK1 N1 N2)......1965 / 2.01
    (_+RIB2 N1 N2).....2153 / 1.83
    (_+STF3 N1 N2).....2589 / 1.52
    (_+ALE3 N1 N2).....3604 / 1.09
    (_+LEE5 N1 N2).....3946 / 1 <slowest>

n1= 400  n2= 800
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+ALE3 N1 N2).....1576 / 1.89 <fastest>
    (_+LEE1 N1 N2).....1591 / 1.87
    (_+LEE5 N1 N2).....1669 / 1.79
    (_+VK1 N1 N2)......1685 / 1.77
    (_+STF3 N1 N2).....2231 / 1.34
    (_+RIB2 N1 N2).....2247 / 1.33
    (_+STF4 N1 N2).....2980 / 1 <slowest>

n1= 8000  n2= 16000
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+RIB2 N1 N2).....1654 / 1.86 <fastest>
    (_+STF4 N1 N2).....1700 / 1.81
    (_+STF3 N1 N2).....1997 / 1.54
    (_+LEE5 N1 N2).....2090 / 1.47
    (_+ALE3 N1 N2).....2699 / 1.14
    (_+VK1 N1 N2)......2870 / 1.07
    (_+LEE1 N1 N2).....3073 / 1 <slowest>

n1= 160000  n2= 320000
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+ALE3 N1 N2).....1591 / 1.78 <fastest>
    (_+STF4 N1 N2).....1700 / 1.67
    (_+STF3 N1 N2).....1857 / 1.53
    (_+LEE5 N1 N2).....1966 / 1.44
    (_+VK1 N1 N2)......2372 / 1.2
    (_+RIB2 N1 N2).....2590 / 1.1
    (_+LEE1 N1 N2).....2839 / 1 <slowest>

n1= 3200000  n2= 6400000
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (_+ALE3 N1 N2).....1592 / 1.62 <fastest>
    (_+LEE1 N1 N2).....1623 / 1.59
    (_+LEE5 N1 N2).....1684 / 1.53
    (_+STF4 N1 N2).....1700 / 1.51
    (_+STF3 N1 N2).....1919 / 1.34
    (_+RIB2 N1 N2).....2246 / 1.15
    (_+VK1 N1 N2)......2574 / 1 <slowest>

[Lee Mac]

A little test:

Code: [Select]

(setq n1 1000000000 n2 2000000000)

3,000,000,000 > 2,147,483,647

I just wanted to point out that some functions do not have the same behavior of the operator "+" that they are replacing.

However, note that the original challenge involved the computation of two integers, and is hence restricted by the upper-limit of the 32-bit signed integer used by AutoLISP. This is more a challenge for academia (and for fun!) as opposed to proposing a replacement of the "+" operator (which can accept any number of numerical arguments, integer or otherwise).

[Marc'Antonio Alessi]

A little test:

Code: [Select]

(setq n1 1000000000 n2 2000000000)

3,000,000,000 > 2,147,483,647

I just wanted to point out that some functions do not have the same behavior of the operator "+" that they are replacing.

However, note that the original challenge involved the computation of two integers, and is hence restricted by the upper-limit of the 32-bit signed integer used by AutoLISP. This is more a challenge for academia (and for fun!) as opposed to proposing a replacement of the "+" operator (which can accept any number of numerical arguments, integer or otherwise).

n1 and n2 are two integers only the sum is over the limit.
Maybe also the "+" AutoLisp function it would need a error control like:  (<= 2147483647 (+ n1 n2)) to return nil on error.

Code: [Select]

(setq n1 1  n2 2147483646) > 2147483646
(<= 2147483647 (+ n1 n2))  > T

(setq n1 1  n2 2147483647) > 2147483647
(<= 2147483647 (+ n1 n2))  > nil


[Marc'Antonio Alessi]

Example:

Code: [Select]

(defun _+Ale4 (a b / r)
  (or _+ (setq _+ (eval (read (chr 43)))))
  (if (<= 2147483647 (setq r (_+ a b))) r)
)

Code: [Select]

(setq n1 1  n2 2147483647) => 2147483647
(_+Ale4  n1 n2)            => nil

(setq n1 1  n2 2147483646) => 2147483646
(_+Ale4  n1 n2)            => 2147483647


[pBe]

(_+Lee6  n1 n2) 713973248
(_+Lee7  n1 n2) > Errore irrecuperabile ***
(_+Ale2  n1 n2) -1294967296
(pbe_+   n1 n2) 2147483647
(_+MkD1  n1 n2) > Errore irrecuperabile ***
(_+Rib1  n1 n2) -1294967296

   Maximum <Max out>

. I guess the code <LM's mod> can be modified to accept real numbers, but then again, since im converting string to numbers and back.. well you guys know what i mean.