# os_mon & alarm_handler in R10B-10

28 messages
12
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Newbie questions

 Raimo Niskanen writes:  > Regarding your problem about determining the number of decimal  > digits in a number, I just came to think of a simple enough  > brute force O(log(N)) or rather O(NN) where NN is the  > number of digits in the number:  >  >     digits(N) when is_integer(N), N >= 0 -> digits(N, 1, 0).  >  >     digits(N, M, D) when M > N -> D;  >     digits(N, M, D) -> digits(N, M*10, D+1). I haven't ever studied bignum implementation, neither for Erlang or in general, but I don't think this solution is O(log N). I would expect M*10 to be expensive, i.e. O(M). And I'm not too sure about the cost of the "M > N" test. Matthias
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Newbie questions

 Matthias Lang writes:  >  > Regarding your problem about determining the number of decimal  >  > digits in a number, I just came to think of a simple enough  >  > brute force O(log(N)) or rather O(NN) where NN is the  >  > number of digits in the number:  >  >  >  >     digits(N) when is_integer(N), N >= 0 -> digits(N, 1, 0).  >  >  >  >     digits(N, M, D) when M > N -> D;  >  >     digits(N, M, D) -> digits(N, M*10, D+1).  >  > I haven't ever studied bignum implementation, neither for Erlang or in  > general, but I don't think this solution is O(log N).  >  > I would expect M*10 to be expensive, i.e. O(M). And I'm not too sure  > about the cost of the "M > N" test. Er, that's wrong too. Bignum multiplication must be implemented as some sort of shift-and-add. Which would make it O(log M), not O(M) as I said. So I expect there to be log M multiplications, each costing log M. That makes the whole thing O(log N * log N). Matthias
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Newbie questions

 In reply to this post by Matthias Lang You are right! I did not think about that. But bignum multiply by smallnum would require O(MM) multiplications plus O(MM) additions with carry where MM is the number of bignum digits (halfwords in the erlang implementation) in the bignum. So the bignum multiplication would be O(log(M)) itself. The comparision would be like a bignum addition which I guess also would be O(MM). Would that result in O(MM*MM) => O(log(M)*log(M))? Note: M > N could be optimized by first checking sign       and then comparing number of bignum digits       followed by comparision on highest bignum digit,       which would be O(1) unless they differ in worst       case the lowest digit which would be O(MM). This       since bignums are represented as a flexible number       of bignum digits (halfwords) of which the highest       must not be zero...       ...Now I checked the code, that was the implementation! [hidden email] (Matthias Lang) writes: > Raimo Niskanen writes: >  > Regarding your problem about determining the number of decimal >  > digits in a number, I just came to think of a simple enough >  > brute force O(log(N)) or rather O(NN) where NN is the >  > number of digits in the number: >  > >  >     digits(N) when is_integer(N), N >= 0 -> digits(N, 1, 0). >  > >  >     digits(N, M, D) when M > N -> D; >  >     digits(N, M, D) -> digits(N, M*10, D+1). > > I haven't ever studied bignum implementation, neither for Erlang or in > general, but I don't think this solution is O(log N). > > I would expect M*10 to be expensive, i.e. O(M). And I'm not too sure > about the cost of the "M > N" test. > > Matthias -- / Raimo Niskanen, Erlang/OTP, Ericsson AB
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Newbie questions

 In reply to this post by Nick Linker Nick Linker <[hidden email]> wrote:         I'm sorry, but I meant quite different question:  given a big         number N, how to compute the number of digits?                 There is obvious solution:  length(integer_to_list(N)), but it         is not very efficient.  I wanted to have a bit faster         solution... Ok, nevermind.         I'm aware of (and have used) several programming languages providing as-long-as-necessary integer arithmetic.  Without consulting manuals (everything is being moved out of my office so that new carpet can be laid) it's hard to be sure, but from memory, NONE of them provides an operation "how many decimal digits in this bignum".  Common Lisp has HAULONG, which tells you about how many BITS, and Java's BigInteger class offers bitLength(), which again tells you how many BITS.  In Smalltalk, the obvious thing to do would be n printString size, and in Scheme it would be (string-length (number->string n)). It's not completely clear what you want.  Is the "number of digits" in -123456890123456890 twenty (literally the number of digits) or twenty-one (the number of characters in the minimal decimal representation)? I must say that the Erlang reference material could be better organised. Trying to answer the question "what are all the predefined operations on numbers" is surprisingly hard. One of the great things about Erlang is that it is open source. emulator/big.c defines a function big_decimal_estimate() which gives an *estimate* of the number of decimal digits; that may be close enough for your needs.  If it's not close enough, big_to_decimal() does the character conversion into a char* buffer, and doesn't build a list. Using emulator/bif.c:integer_to_list as a model, it would be quite easy to write a new BIF that gave you the number of decimal digits in a number. The question remains, WHY?  For what kind of problem is it useful to know the number of decimal digits but NOT what the digits actually are? And would avoiding the list construction actually buy you very much? It must be O(#Digits) work to build the list, but finding out what the digits are is O(#Digits**2). I benchmarked the following code against length(integer_to_list(N)), for the first however many factorials.  The two seemed to be about the same speed.  Your mileage will of course vary. integer_digits(N) when integer(N) ->     if N >= 0 -> natural_digits_loop(N, 0)      ; N <  0 -> natural_digits_loop(-N, 1)     end. natural_digits(N) when integer(N), N >= 0 ->     natural_digits_loop(N, 0). natural_digits_loop(N, D) when N >= 10000 ->     natural_digits_loop(N div 10000, D + 4); natural_digits_loop(N, D) when N >= 1000 ->     D + 4; natural_digits_loop(N, D) when N >= 100 ->     D + 3; natural_digits_loop(N, D) when N >= 10 ->     D + 2; natural_digits_loop(_, D) ->     D + 1.
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Newbie questions

 Raimo Niskanen <[hidden email]> wrote:         Regarding your problem about determining the number of decimal         digits in a number, I just came to think of a simple enough         brute force O(log(N)) or rather O(NN) where NN is the         number of digits in the number:                     digits(N) when is_integer(N), N >= 0 -> digits(N, 1, 0).                     digits(N, M, D) when M > N -> D;             digits(N, M, D) -> digits(N, M*10, D+1).         I am reading "O(NN)" as "O(#Digits)". Unfortunately, this is O(#Digits**2), because the multiplication M*10 is O(#Digits), not O(1).
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Newbie questions

 In reply to this post by Richard O'Keefe Richard A. O'Keefe writes:  > Nick Linker <[hidden email]> wrote:  > I'm sorry, but I meant quite different question:  given a big  > number N, how to compute the number of digits?  >  > There is obvious solution:  length(integer_to_list(N)), but it  > is not very efficient.  I wanted to have a bit faster  > solution... Ok, nevermind.  >  > I'm aware of (and have used) several programming languages providing  > as-long-as-necessary integer arithmetic.  Without consulting manuals  > (everything is being moved out of my office so that new carpet can  > be laid) it's hard to be sure, but from memory, NONE of them provides  > an operation "how many decimal digits in this bignum".  Common Lisp  > has HAULONG, which tells you about how many BITS, and Java's  > BigInteger class offers bitLength(), which again tells you how many  > BITS.  In Smalltalk, the obvious thing to do would be n printString size,  > and in Scheme it would be (string-length (number->string n)). You seem to have your Lisps confused :-). Haulong is a function in MacLisp; the corresponding operation in Common Lisp is integer-length. Both functions give the length of the integer in bits.  > It's not completely clear what you want.  Is the "number of digits"  > in -123456890123456890 twenty (literally the number of digits) or  > twenty-one (the number of characters in the minimal decimal representation)? Curiously, both CL's integer-length and Java's bitLength() define the length of negative numbers so that -1 has length 0 (same as the length of 0, of course). Sven-Olof
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Newbie questions

 [hidden email] (Sven-Olof Nystr|m) writes: > Richard A. O'Keefe writes: >  > Nick Linker <[hidden email]> wrote: >  > I'm sorry, but I meant quite different question:  given a big >  > number N, how to compute the number of digits? >  > >  > There is obvious solution:  length(integer_to_list(N)), but it >  > is not very efficient.  I wanted to have a bit faster >  > solution... Ok, nevermind. >  > >  > I'm aware of (and have used) several programming languages providing >  > as-long-as-necessary integer arithmetic.  Without consulting manuals >  > (everything is being moved out of my office so that new carpet can >  > be laid) it's hard to be sure, but from memory, NONE of them provides >  > an operation "how many decimal digits in this bignum".  Common Lisp >  > has HAULONG, which tells you about how many BITS, and Java's >  > BigInteger class offers bitLength(), which again tells you how many >  > BITS.  In Smalltalk, the obvious thing to do would be n printString size, >  > and in Scheme it would be (string-length (number->string n)). > > > You seem to have your Lisps confused :-). Haulong is a function in > MacLisp; the corresponding operation in Common Lisp is > integer-length. Both functions give the length of the integer in bits. > >  > It's not completely clear what you want.  Is the "number of digits" >  > in -123456890123456890 twenty (literally the number of digits) or >  > twenty-one (the number of characters in the minimal decimal representation)? > > Curiously, both CL's integer-length and Java's bitLength() define the > length of negative numbers so that -1 has length 0 (same as the length > of 0, of course). > That seems to be some kind of 2-complement notion of bit length. If you define the bit length of negative numbers to be the number of bits from the right to the last non-1 as opposed to for positive numbers to the last non-0, you would get this. > > Sven-Olof > -- / Raimo Niskanen, Erlang/OTP, Ericsson AB