Topic: -= {Challenge} =- convert an hexadecimal into a decimal

[ElpanovEvgeniy]

suggesting a new challenge
need to transfer a number from hexadecimal to decimal format.
The difficulty is that the resulting decimal number may be greater than 2147483647

example:

Code: [Select]

(hex2dec "7ffffcf5c20") ;=>>      "8796089834528"
(hex2dec "1234567890abcdef") ;=>> "1311768467294899695"
(hex2dec "fedcba0987654321") ;=>> "18364757930599072545"
(hex2dec "111111111111") ;=>>     "18764998447377"
(hex2dec "ffffffffffff") ;=>>     "281474976710655"

[ElpanovEvgeniy]

Sorry, I found a bug in my code, changed answers in the test examples!

[gile]

Hi,

I have a solution, but it doesn't display good results for very big numbers.

Code: [Select]

(defun hex2dec (hex / r c)
  (setq r 0.)
  (foreach c (vl-string->list (strcase hex))
    (setq r (+
      (* 16. r)
      (-
c
(if (<= c 57)
  48.
  55.
)
      )
    )
    )
  )
  (rtos r 2 0)
)

_$ (hex2dec "7ffffcf5c20")
"8796089834528"
_$ (hex2dec "111111111111")
"18764998447377"
_$ (hex2dec "ffffffffffff")
"281474976710655"

but:

_$ (hex2dec "1234567890abcdef")
"1E+18"
_$ (hex2dec "fedcba0987654321")
"2E+19"

[Lee Mac]

Code: [Select]

(defun hex2dec ( n )
    (defun _ascii2int ( x )
        (- x (if (< x 58) 48.0 55.0))
    )
    (defun _hex2dec ( l )
        (if l (+ (* 16.0 (_hex2dec (cdr l))) (_ascii2int (car l))) 0)
    )
    (defun _dec2str ( n x / d )
        (if (< 0 n)
            (progn
                (setq d (rem (/ n x) 1))
                (strcat (_dec2str (- n (* x d)) (* x 10.0)) (rtos (* 10 d) 2 0))
            )
            ""
        )
    )
    (_dec2str (_hex2dec (reverse (vl-string->list (strcase n)))) 10.0)
)

Code: [Select]

(hex2dec "7ffffcf5c20") ;=>>      "8796089834528"
(hex2dec "1234567890abcdef") ;=>> "1311768467294899800"
(hex2dec "fedcba0987654321") ;=>> "18364757930599073000"
(hex2dec "111111111111") ;=>>     "18764998447377"
(hex2dec "ffffffffffff") ;=>>     "281474976710655"
 

[ElpanovEvgeniy]

Hi gile!
You left quite a bit.

[ElpanovEvgeniy]

Hi Lee Mac!
In your code has a bug.
See if you have
(hex2dec "1234567890abcdef"); =>> "1311768467294899800"
must
(hex2dec "1234567890abcdef"); =>> "1311768467294899695"

[ElpanovEvgeniy]

An example of how to check the code if the number is not great ...

[David Bethel]

I hit the same stumbling block:

Code: [Select]


(defun hex2dec (s / e c l)
;;;SINGLE HEX STRING 0-F to Decimal Conversion
(defun hex2dec1 (s / n)
 (setq n (ascii (strcase s)))
 (- n (if (> n 57) 55 48)))

  (setq e 0
        s (strcase s))
  (while (> (strlen s) 0)
         (setq c (substr s (strlen s) 1)
               s (substr s 1 (1- (strlen s)))
               l (cons (* (hex2dec1 c) (expt 2 e)) l)
               e (+ e 4)))
(apply '+ l))

Anything bigger than (expt 2 30) gives bad results.  -David

[ElpanovEvgeniy]

I hit the same stumbling block:

source of the problem:

Code: [Select]

(1+ 2147483647) = -2147483648

[JohnK]

The number 2147483647 is the largest value you can have for a signed int. In C++ you would have to use an unsigned int which would allow you to have an int with a value of 4294967295.

Code: [Select]

(defun bin? (nu / lst nu)
  (while (not (= nu 0))
         (setq lst (cons (rem nu 2) lst)
               nu (/ nu 2)))
  lst
 )

Command: (bin? 2147483647)
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

Command: (length (bin? 2147483647))
31

[ElpanovEvgeniy]

The number 2147483647 is the largest value you can have for a signed int. In C++ you would have to use an unsigned int which would allow you to have an int with a value of 4294967295.

but that does not stop to consider list or texts, for the storage of any size integer 

[JohnK]

but that does not stop to consider list or texts, for the storage of any size integer 

That is what I would do too.

[gile]

This is much easier with F# wich has a BigInterger type.

Code: [Select]

let hex2dec (hex : string) =
    let rec foo chrs result =
        match chrs with
        | [] -> result
        | h :: t -> foo t (16I * result + h - (if h <= 57I then 48I else 55I))
    string (foo (hex.ToUpper() |> Seq.toList |> List.map (fun c -> bigint(int c))) 0I)

Code: [Select]

> hex2dec "7ffffcf5c20" ;;
val it : string = "8796089834528"
> hex2dec "1234567890abcdef" ;;
val it : string = "1311768467294899695"
> hex2dec "fedcba0987654321" ;;
val it : string = "18364757930599072545"
> hex2dec "111111111111" ;;
val it : string = "18764998447377"
> hex2dec "ffffffffffff" ;;
val it : string = "281474976710655"

[ElpanovEvgeniy]

This is much easier with F# wich has a BigInterger type.

This is a good way, if you know F # and agree to include it in your project.
My path was through the lisp ... 

[JohnK]

Idea for calculating the list or string length:
(0 . 31) = 2147483647 = 31
(1 . 1) =  2147483648 = 32
(1 . 2) =  2147483649 = 32
...

or something like that.

[ElpanovEvgeniy]

My program also works with any number of dimensions, without limitation, as BigInterger...
The same, I look to you. 

Code: [Select]

(setq s "ffffffffffffffffffffffffffffffffffffffffffffffffff")
(strlen s) ;=>> 50
(hex2dec "ffffffffffffffffffffffffffffffffffffffffffffffffff")
;=>> "1606938044258990275541962092341162602522202993782792835301375"

[ElpanovEvgeniy]

The problem was born from the need to create a field in AutoCAD 2008 x64 sp1

Code: [Select]

(vla-get-Utility (vla-get-ActiveDocument (vlax-get-acad-object)))
no method 'GetObjectIDString

Code: [Select]

(vlax-invoke
  (vla-get-Utility (vla-get-ActiveDocument (vlax-get-acad-object)))
  'GetObjectIDString
  (vlax-ename->vla-object (car (entsel)))
)
returns

Code: [Select]

; error: ActiveX Server returned the error: unknown name: "GETOBJECTIDSTRING"
_$

[Lee Mac]

Hi Lee Mac!
In your code has a bug.
See if you have
(hex2dec "1234567890abcdef"); =>> "1311768467294899800"
must
(hex2dec "1234567890abcdef"); =>> "1311768467294899695"

I noticed - I think this is due to the accuracy lost when dividing doubles. I shall have to consider another method, perhaps looking at the patterns of the digits of multiples of 16.

[irneb]

Exactly! I get a similar, yet slightly different error using my general purpose routines:

Code: [Select]

_$ (dec->string (base->dec "7ffffcf5c20" 16))
"879689834528"
_$ (dec->string (base->dec "1311768467294899695" 16))
"5627943617999796174848"
_$ (dec->string (base->dec "1234567890abcdef" 16))
"1311768467294899712"
_$ (dec->string (base->dec "fedcba0987654321" 16))
"18364757930599071744"
_$ (dec->string (base->dec "111111111111" 16))
"18764998447377"
_$ (dec->string (base->dec "ffffffffffff" 16))
"281474976710655"

[ElpanovEvgeniy]

Exactly! I get a similar, yet slightly different error using my general purpose routines:

Code: [Select]

_$ (dec->string (base->dec "7ffffcf5c20" 16))
"879689834528"
_$ (dec->string (base->dec "1311768467294899695" 16))
"5627943617999796174848"
_$ (dec->string (base->dec "1234567890abcdef" 16))
"1311768467294899712"
_$ (dec->string (base->dec "fedcba0987654321" 16))
"18364757930599071744"
_$ (dec->string (base->dec "111111111111" 16))
"18764998447377"
_$ (dec->string (base->dec "ffffffffffff" 16))
"281474976710655"

Great job!
It remains a bit:

Code: [Select]

(dec->string (base->dec  "1234567890abcdef" 16)); =>> "1311768467294899712"must

Code: [Select]

(hex2dec "1234567890abcdef"); =>> "1311768467294899695"

[irneb]

That's what I meant about a "slightly different error". Though I think it's due to the way I change a float into a string. The division by a number other than a factor of 2 would usually cause floating point errors. One of the reasons I have a (> frac 1.e-10) in that routine instead of simply a (> frac 0.).

I wonder if one shouldn't rather implement something like a BCD number system for this case. Though it seems to get to that one might just as well implement a BigNum through a list structure. Yet another point where AutoLisp has fallen behind CL. That 2147483647 is the maximum 32bit signed integer value available, now with 64bit programs it's just not good enough for stuff like ID's.

[ElpanovEvgeniy]

Yet another point where AutoLisp has fallen behind CL. That 2147483647 is the maximum 32bit signed integer value available, now with 64bit programs it's just not good enough for stuff like ID's.

I had the 46 line, to solve the task ...

[VovKa]

translated from the stolen vb code

Code: [Select]

(defun vk_BaseToBase (h ib ob / lst n)
  (repeat (1+ (fix (* (strlen h) (/ (log ib) (log ob))))) (setq lst (cons 0 lst)))
  (foreach c (vl-string->list h)
    (setq n   (- c
(if (< c 58)
   48
   55
)
      )
  lst (mapcar (function (lambda (d)
  (setq d (+ (* d ib) n)
n (/ d ob)
  )
  (rem d ob)
)
      )
      lst
      )
    )
  )
  (apply 'strcat
(reverse (mapcar (function (lambda (c)
      (chr (+ c
      (if (< c 10)
48
55
      )
   )
      )
    )
  )
  lst
  )
)
  )
)
;;;(vk_BaseToBase (vk_BaseToBase "FFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 16 10) 10 16)

[ElpanovEvgeniy]

translated from the stolen vb code

Code: [Select]

(defun vk_BaseToBase (h ib ob / lst n)
  (repeat (1+ (fix (* (strlen h) (/ (log ib) (log ob))))) (setq lst (cons 0 lst)))
  (foreach c (vl-string->list h)
    (setq n   (- c
(if (< c 58)
   48
   55
)
      )
  lst (mapcar (function (lambda (d)
  (setq d (+ (* d ib) n)
n (/ d ob)
  )
  (rem d ob)
)
      )
      lst
      )
    )
  )
  (apply 'strcat
(reverse (mapcar (function (lambda (c)
      (chr (+ c
      (if (< c 10)
48
55
      )
   )
      )
    )
  )
  lst
  )
)
  )
)
;;;(vk_BaseToBase (vk_BaseToBase "FFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 16 10) 10 16)

Code: [Select]

(setq s "FFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
(strlen s) ;== 29
(strlen (vk_BaseToBase (vk_BaseToBase s 16 10) 10 16)) ;== 30

[VovKa]

yep, leading zeros to be removed via vl-string-left-trim

[ElpanovEvgeniy]

yep, leading zeros to be removed via vl-string-left-trim

You did a very concise program!
My version is somewhat more complicated ...

[Lee Mac]

Not as clean as VovKa's:

Code: [Select]

(defun hex2dec ( str / l1 l2 mat pas vec x x1 )
    (setq vec (mapcar '(lambda ( x ) (- x (if (< x 58) 48 55))) (vl-string->list (strcase str)))
          pas (_pascalmatrix (length vec) '((1.0)))
          mat pas
    )
    (repeat 5 (setq mat (mxm mat pas)))
    (setq l1 (reverse (vxm vec mat))
          x1 (car l1)
    )
    (while (< 0 x1)
        (setq l2 (cons (chr (+ (fix (rem x1 10)) 48)) l2)
              l1 (cdr l1)
              x1 (+ (/ (fix x1) 10) (cond ((car l1)) (0)))
        )
    )
    (apply 'strcat l2)
)

(defun _pascalmatrix ( n l )
    (if (< n 2)
        l
        (_pascalmatrix (1- n)
            (cons
                (mapcar '+ (cons 0.0 (car l)) (append (car l) '(0.0)))
                (mapcar (function (lambda ( x ) (cons 0.0 x))) l)
            )
        )
    )
)

;; Matrix Transpose - Doug Wilson
;; Args: m - nxn matrix

(defun trp ( m )
    (apply 'mapcar (cons 'list m))
)

;; Matrix x Matrix - Vladimir Nesterovsky
;; Args: m,n - nxn matrices

(defun mxm ( m n )
    ( (lambda ( a ) (mapcar '(lambda ( r ) (mxv a r)) m)) (trp n))
)

;; Matrix x Vector - Vladimir Nesterovsky
;; Args: m - nxn matrix, v - vector in R^n

(defun mxv ( m v )
    (mapcar '(lambda ( r ) (apply '+ (mapcar '* r v))) m)
)

(defun vxm ( v m )
    (mapcar '(lambda ( r ) (apply '+ (mapcar '* r v))) (trp m))
)
Using the algorithm described here.

[ElpanovEvgeniy]

Hi Lee Mac!
Great job!
Program is working properly.

[ElpanovEvgeniy]

my version:

Code: [Select]

(defun eea-hex2dec (s / L f1 f2 f3 f4 f5)
  (defun f1 (s)
    (mapcar (function (lambda (a)
                        (- a
                           (if (<= a 57)
                             48
                             55
                           )
                        )
                      )
            )
            (vl-string->list (strcase s))
    )
  )
  (defun f3 (i)
    (defun f2 (i)
      (if (> i 9)
        (append (f2 (/ i 10)) (f2 (rem i 10)))
        (list i)
      )
    )
    (reverse (f2 i))
  )
  (defun f4 (l)
    (if l
      (cons (car l) (f4 (mapcar (function (lambda (a) (cons 0 a))) (cdr l))))
    )
  )
  (defun f5 (l / f)
    (if l
      (cons (apply (function +) (mapcar (function car) l)) (f5 (vl-remove nil (mapcar (function cdr) l))))
    )
  )
  (setq s (f1 s)
        l '(0)
  )
  (while s
    (setq l (mapcar (function (lambda (a) (* a 16))) l)
          l (cons (+ (car l) (car s)) (cdr l))
          s (cdr s)
    )
    (setq l (f5 (f4 (mapcar (function f3) l))))
  )
  (while (vl-some (function (lambda (a) (> a 9))) l) (setq l (f5 (f4 (mapcar (function f3) l)))))
  (apply (function strcat) (mapcar (function itoa) (reverse l)))
)

[Lee Mac]

Very nice algorithm VovKa 

[VovKa]

You did a very concise program!
My version is somewhat more complicated ...

Very nice algorithm VovKa 

thanx guys, but, as i wrote earlier, the algo is not mine. i've just translated the code to lisp. that was a couple of years ago
i'm googling for the original article for half an hour or so, but can't find it

[Lee Mac]

This is an interesting modification to see the progression: 

Code: [Select]

(defun vk_BaseToBase ( h ib ob / lst n )
    (repeat (1+ (fix (* (strlen h) (/ (log ib) (log ob))))) (setq lst (cons 0 lst)))
    (foreach c (vl-string->list (strcase h))
        (setq n (- c (if (< c 58) 48 55)))
        (setq lst
            (mapcar
                (function
                    (lambda ( d )
                        (setq d (+ (* d ib) n) n (/ d ob))
                        (rem d ob)
                    )
                )
                lst
            )
        )
        (print lst)
    )
    (apply 'strcat
        (reverse
            (mapcar
                (function
                    (lambda (c) (chr (+ c (if (< c 10) 48 55))))
                )
                lst
            )
        )
    )
)

Code: [Select]

_$ (vk_BaseToBase "7DB" 16 10)

(7 0 0 0)
(5 2 1 0)
(1 1 0 2) "2011"

[gile]

Very nice codes guys !

My regret today, is to have been too lazy to go further searching a nice LISP solution for this challenge.
It would have been my little tribute to John McCarthy...

[ElpanovEvgeniy]

my new version:

Code: [Select]

(defun eea-hex2dec (s / L f1 f2 f3)
  ;; By ElpanovEvgeniy
  ;; 26.10.2011
  (defun f1 (i)
    (if (> i 9)
      (append (f1 (rem i 10)) (f1 (/ i 10)))
      (list i)
    )
  )
  (defun f2 (l)
    (if l
      (cons (car l) (f2 (mapcar (function (lambda (a) (cons 0 a))) (cdr l))))
    )
  )
  (defun f3 (l / f)
    (if l
      (cons (apply (function +) (mapcar (function car) l)) (f3 (vl-remove nil (mapcar (function cdr) l))))
    )
  )
  (setq s (mapcar (function (lambda (a) (- a 48)))
                  (vl-string->list (vl-string-translate "abcdef" ":;<=>?" s))
          )
        l '(0)
  )
  (foreach a s
    (setq l (cons (+ (* 16 (car l)) a) (mapcar (function (lambda (a) (* a 16))) (cdr l)))
          l (f3 (f2 (mapcar (function f1) l)))
    )
  )
  (while (vl-some (function (lambda (a) (> a 9))) l) (setq l (f3 (f2 (mapcar (function f1) l)))))
  (apply (function strcat) (mapcar (function itoa) (reverse l)))
)

[ElpanovEvgeniy]

my new version:

Code: [Select]

(defun eea-hex2dec (s / f)
  ;; By ElpanovEvgeniy
  ;; 27.10.2011
  (defun f (l n s)
    (cond ((and (> n 9) (not l)) (f '(0) n nil))
          ((and n l)
           (f (cons (rem (+ (* (car l) 16) n) 10) (f (cdr l) (/ (+ (* (car l) 16) n) 10) nil)) (car s) (cdr s))
          )
          (l)
          ((list n))
    )
  )
  (setq s (mapcar (function (lambda (a) (- a 48)))
                  (vl-string->list (vl-string-translate "ABCDEF" ":;<=>?" (strcase s)))
          )
  )
  (apply (Function strcat) (mapcar (function itoa) (reverse (f '(0) (car s) (cdr s)))))
)

[ElpanovEvgeniy]

new version:

Code: [Select]

(defun hex2dec (s / f)
  ;; By ElpanovEvgeniy
  ;; 27.10.2011
  (defun f (l s / a)
    (cond ((and s l) (f (cons (rem (setq a (+ (* (car l) 16) (car s))) 10) (f (cdr l) (list (/ a 10)))) (cdr s)))
          ((> (car s) 9) (f nil (cons (rem (car s) 10) (f nil (list (/ (car s) 10))))))
          (l)
          ((if (not (equal s '(0))) s nil))
    )
  )
  (setq s (mapcar (function (lambda (a) (- a 48))) (vl-string->list (vl-string-translate "ABCDEF" ":;<=>?" (strcase s)))))
  (apply (Function strcat) (mapcar (function itoa) (reverse (f '(0) s))))
)

[Lee Mac]

Someone's been busy! 

I shall have to take some time to study these 

[Lee Mac]

Evgeniy,

This:

Code: [Select]

((if (not (equal s '(0))) s nil))
could be reduced to:

Code: [Select]

((not (equal s '(0))) s)
 


Fantastic code.

[ElpanovEvgeniy]

Evgeniy,

This:

Code: [Select]

((if (not (equal s '(0))) s nil))
could be reduced to:

Code: [Select]

((not (equal s '(0))) s)
 


Fantastic code.

Mistakes really fantastic     

[Lee Mac]

Not quite as succinct as some of the other functions, but here is another entry:

Code - Auto/Visual Lisp: [Select]

1. ;; Hex to Decimal String  -  Lee Mac
2. ;; Returns the decimal representation of a supplied hexadecimal string
3.  
4. (defun LM:hex->decstr ( hex / foo bar )
5.     (defun foo ( lst rtn )
6.         (if lst
7.             (foo (cdr lst) (bar (- (car lst) (if (< 57 (car lst)) 55 48)) rtn))
8.             (apply 'strcat (mapcar 'itoa (reverse rtn)))
9.         )
10.     )
11.     (defun bar ( int lst )
12.         (if lst
13.             (if (or (< 0 (setq int (+ (* 16 (car lst)) int))) (cdr lst))
14.                 (cons (rem int 10) (bar (/ int 10) (cdr lst)))
15.             )
16.             (bar int '(0))
17.         )
18.     )
19.     (foo (vl-string->list (strcase hex)) nil)
20. )

Code - Auto/Visual Lisp: [Select]

1. _$ (LM:hex->decstr "1234567890abcdef")
2. "1311768467294899695"

[squirreldip]

Here's a stab at it...

Code - Auto/Visual Lisp: [Select]

1. (defun HEX2DEC (S / D N SL STR+)
2.  (defun STR+ (A B / C D S)
3.   (setq A (vl-list->string (reverse (vl-string->list A))))
4.   (setq B (vl-list->string (reverse (vl-string->list B))))
5.   (setq D "")
6.   (setq C 0)
7.   (while (or (/= A "") (/= B ""))
8.    (setq S (+ C (atoi (substr A 1 1)) (atoi (substr B 1 1))))
9.    (if (>= S 10)
10.     (setq C 1 S (- S 10))
11.     (setq C 0)
12.    )
13.    (setq D (strcat (itoa S) D))
14.    (setq A (substr A 2) B (substr B 2))
15.   )
16.   (if (= C 1) (setq D (strcat "1" D)))
17.   D
18.  )
19.  (setq D "0")
20.  (setq SL (vl-string->list (strcase S)))
21.  (foreach N SL
22.   (repeat 4
23.    (setq D (STR+ D D))
24.   )
25.   (setq N (itoa (- N (if (< N 65) 48 55))))
26.   (setq D (STR+ D N))
27.  )
28.  D
29. )

Code - Auto/Visual Lisp: [Select]

1. (hex2dec "7ffffcf5c20") ;=>> "8796089834528"
2. (hex2dec "1234567890abcdef") ;=>> "1311768467294899695"
3. (hex2dec "fedcba0987654321") ;=>> "18364757930599072545"
4. (hex2dec "111111111111") ;=>> "18764998447377"
5. (hex2dec "ffffffffffff") ;=>> "281474976710655"
6.  
7. and a big one:
8. (hex2dec "fedcba0987654321fedcba0987654321fedcba0987654321fedcba0987654321") ;=>> "115277453876119746492122989728511096337595255118815003943225442645743491171105"