Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #41078 > unrolled thread

Strings and numbers

Back to article view | Back to comp.lang.forth

Contents

  Strings and numbers Steve Graham <solitary.wanderer52@gmail.com> - 2015-08-03 13:24 -0700
    Re: Strings and numbers Julian Fondren <julian.fondren@gmail.com> - 2015-08-03 13:51 -0700
      Re: Strings and numbers "Rod Pemberton" <boo@fasdfrewar.cdm> - 2015-08-03 17:38 -0400
      Re: Strings and numbers Steve Graham <solitary.wanderer52@gmail.com> - 2015-08-03 14:44 -0700
    Re: Strings and numbers Paul Rubin <no.email@nospam.invalid> - 2015-08-03 20:59 -0700
      Re: Strings and numbers Steve Graham <solitary.wanderer52@gmail.com> - 2015-08-04 12:19 -0700
        Re: Strings and numbers "WJ" <w_a_x_man@yahoo.com> - 2015-08-07 09:29 +0000
          Re: Strings and numbers "WJ" <w_a_x_man@yahoo.com> - 2015-09-04 15:14 +0000
            Re: Strings and numbers "WJ" <w_a_x_man@yahoo.com> - 2015-09-07 19:34 +0000
              Re: Strings and numbers Julian Fondren <julian.fondren@gmail.com> - 2015-09-08 11:48 -0700
              Re: Strings and numbers Paul Rubin <no.email@nospam.invalid> - 2015-09-09 00:41 -0700
                Re: Strings and numbers Richard Todd <richard.wesley.todd@gmail.com> - 2015-09-10 00:32 -0700
                  Re: Strings and numbers Richard Todd <richard.wesley.todd@gmail.com> - 2015-09-10 10:29 -0700
                    Re: Strings and numbers Paul Rubin <no.email@nospam.invalid> - 2015-09-10 17:22 -0700
                      Re: Strings and numbers Richard Todd <richard.wesley.todd@gmail.com> - 2015-09-10 21:34 -0700
                        Re: Strings and numbers humptydumpty <ouatubi@gmail.com> - 2015-09-11 02:16 -0700
                          Re: Strings and numbers humptydumpty <ouatubi@gmail.com> - 2015-09-11 07:33 -0700
                            Re: Strings and numbers Paul Rubin <no.email@nospam.invalid> - 2015-09-13 00:12 -0700
                              Re: Strings and numbers humptydumpty <ouatubi@gmail.com> - 2015-09-13 02:09 -0700
                        Re: Strings and numbers Paul Rubin <no.email@nospam.invalid> - 2015-09-11 15:53 -0700
                          Re: Strings and numbers Andrew Haley <andrew29@littlepinkcloud.invalid> - 2015-12-18 16:02 -0600
              Re: Strings and numbers "WJ" <w_a_x_man@yahoo.com> - 2015-09-12 23:38 +0000
                Re: Strings and numbers "WJ" <w_a_x_man@yahoo.com> - 2015-09-13 19:41 +0000
              Re: Strings and numbers "WJ" <w_a_x_man@yahoo.com> - 2015-11-29 18:09 +0000

Page 2 of 2 — ← Prev page 1 [2]

#44291

Sorry to reply to an old post, but I think this is interesting.

Paul Rubin <no.email@nospam.invalid> wrote:
> Richard Todd <richard.wesley.todd@gmail.com> writes:
>> using an exception for returning a normal value is another kind of
>> smell, is it not?
> 
> I actually don't know, and will defer to the Forth gurus about that (I'm
> far from one).  It's idiomatic in Lisp to use catch/throw that way, so I
> went with it.  It's frowned on in Java but I think that's because Java
> exceptions are slow and heavy.

Not always, it's a matter of style that exceptions are exceptional,
but you don't have to do it that way.

In Java, when you create an exception the whole stack is traced and a
backtrace is stored in the exception for diagnostic purposes.  This is
indeed expensive.  However, you don't need to create a new exception
every time you throw one.  You can use a pregenerated exception, and
this is sensible if you expect to be throwing a lot.

In this example the exception is passed into the method (it can be
statically allocated, or stored in a field somewhere).

    long clutter(Exception e) throws Exception {
        long val = r.nextLong();
        if ((val & 15) == 0)
            throw e;
        return val;
    }

    long clatter(Exception e) {
        long val;
        try {
            val = clutter(e);
        } catch (Exception ex) {
            val = -1024;
        }
        return val;
    }

The generated code looks like this:

      ldr       x1, [x1,#16]    ;*getfield r
      str       x2, [sp]        ; save Exception e on the stack
      cbz       x1, throw NullPointerException if r is null
      bl        r.nextLong
      and       x10, x0, #0xf
      cbz       x10, catch_label
      ... Remove frame and return

catch_label:
      ldr       x10, [sp]
      cbz       x10, Throw NullPointerException if e is null
      orr       x0, xzr, #0xfffffffffffffc00
      ... Remove frame and return

The compiler has inlined clutter and noticed that the throw is really
just a goto, and generated code accordingly.  It is certainly true
that if clutter isn't inlined then throwing the exception will be far
more expensive: we'll have to unwind the stack, searching for handlers
and undoing locks as we go.  Like so much else in Java, inlining is
the key to good performace.

> I haven't studied how catch/throw is implemented in Forth but I'm
> imagining it to be a setjmp/longjmp style mechanism where the catch
> handlers are linked through the R stack, with the innermost one
> remembered in a static cell, and the handler mostly just restores
> the old DP and RP.  So if it works that way, it should be
> lightweight and fast.

Yes, that's the idea.  The only downside is that catch blocks have the
small overhead of maintaining a chain of handlers.

Andrew.

[toc] | [prev] | [next] | [standalone]

#41977

WJ wrote:

> WJ wrote:
> 
> > WJ wrote:
> > 
> > > Steve Graham wrote:
> > > 
> > > > 
> > > > http://programmingpraxis.com/2015/07/21/a-number-puzzle/#comments
> > > 
> > > 
> > > 
> > > >  Find a 10-digit number, with all digits unique, such that the first n
> > > >  digits of the number are divisible by n. For instance, in the 3-digit
> > > >  number 345, the 1-digit prefix, 3, is divisible by 1, the 2-digit
> > > >  prefix, 34, is divisible by 2, and the 3-digit prefix, 345, is
> > > >  divisible by 3.
> > > 
> > > Gauche Scheme:
> > > 
> > > (define (next divisor integer digits)
> > >   (filter-map
> > >     (lambda (d)
> > >       (let1 new-int (+ (* 10 integer) d)
> > >         (and (zero? (mod new-int divisor))
> > >              (list new-int (delete d digits)))))
> > >     digits))
> > > 
> > > 
> > > ;; Recursion.
> > > (let go ((divisor 1) (candidates (list (list 0 (iota 10)))))
> > >   (if (> divisor 10)
> > >     (caar candidates)
> > >     (go (+ divisor 1)
> > >         (append-map
> > >           (lambda (x) (apply next divisor x))
> > >           candidates))))
> > > 
> > > 3816547290
> > 
> > Ruby:
> > 
> > def next_digit( divisor, digits_so_far )
> >   number_so_far = digits_so_far.join.to_i * 10
> >   ((0..9).to_a - digits_so_far).select{|d|
> >     ((number_so_far + d).modulo divisor).zero? }.
> >     map{|d| digits_so_far + [d]}
> > end
> > 
> > candidates = [[]]
> > 1.upto(10){|divisor|
> >   candidates = candidates.map{|digit_list|
> >     next_digit( divisor, digit_list) }.flatten(1) }
> > candidates
> > 
> >  ===>
> > [[3, 8, 1, 6, 5, 4, 7, 2, 9, 0]]
> 
> No one has yet posted a Forth solution.  Perhaps this Ruby version
> will be more understandable than the previous one.
> 
> def divisible( n, divisor )
>   n.modulo(divisor).zero?
> end
> 
> def one_more_digit( divisor, digits_so_far )
>   digits_avail = (0 .. 9).to_a - digits_so_far
>   base_for_new_number = digits_so_far.join.to_i * 10
>   digits_avail.select{ |d| divisible( base_for_new_number + d, divisor )}.
>     map{|d| digits_so_far + [d] }
> end
> 
> 
> Here's an example of how this function works:
> 
> one_more_digit( 4, [3, 8, 1] )
>     ==>[[3, 8, 1, 2], [3, 8, 1, 6]]
> 
> 
> 
> candidates = [[]]
> 1.upto(10){|divisor|
>   candidates = candidates.map{|digit_list|
>     one_more_digit( divisor, digit_list) }.flatten(1) }
> candidates
> 
> [[3, 8, 1, 6, 5, 4, 7, 2, 9, 0]]
> 
> Here's an example of how the "flatten" command works in Ruby:
> 
> [[[3, 8, 1, 2], [3, 8, 1, 6]]].flatten
>     ==>[3, 8, 1, 2, 3, 8, 1, 6]
> [[[3, 8, 1, 2], [3, 8, 1, 6]]].flatten(1)
>     ==>[[3, 8, 1, 2], [3, 8, 1, 6]]


Oforth:

: flatten-1 { [] swap apply( #+ ) }

: digits-avail( digits-used )
  { seqFrom(0,9) filter( #[ digits-used include not ] ) }

: divisible( divisor, list-of-digits )
  { list-of-digits asString asInteger isMultiple( divisor ) }

: one-more-digit( divisor, digits-so-far )
{ digits-so-far digits-avail map( #[ digits-so-far swap + ] )
  filter( #[ divisible( divisor ) ] ) }

: go( divisor, candidates )
{ divisor 10 >
  ifTrue: [ candidates println ]
  else: [ candidates map( #[ one-more-digit(divisor) ] )
    flatten-1  divisor 1 +  go ] }

go(1, [[]])

[[3, 8, 1, 6, 5, 4, 7, 2, 9, 0]]

[toc] | [prev] | [next] | [standalone]

#41984

WJ wrote:


> 
> : digits-avail( digits-used )
>   { seqFrom(0,9) filter( #[ digits-used include not ] ) }


: digits-avail( digits-used )
  { seqFrom(0,9) stripAll( digits-used ) }

[toc] | [prev] | [next] | [standalone]

#43938

WJ wrote:

> WJ wrote:
> 
> > WJ wrote:
> > 
> > > Steve Graham wrote:
> > > 
> > > > 
> > > > http://programmingpraxis.com/2015/07/21/a-number-puzzle/#comments
> > > 
> > > 
> > > 
> > > >  Find a 10-digit number, with all digits unique, such that the first n
> > > >  digits of the number are divisible by n. For instance, in the 3-digit
> > > >  number 345, the 1-digit prefix, 3, is divisible by 1, the 2-digit
> > > >  prefix, 34, is divisible by 2, and the 3-digit prefix, 345, is
> > > >  divisible by 3.
> > > 
> > > Gauche Scheme:
> > > 
> > > (define (next divisor integer digits)
> > >   (filter-map
> > >     (lambda (d)
> > >       (let1 new-int (+ (* 10 integer) d)
> > >         (and (zero? (mod new-int divisor))
> > >              (list new-int (delete d digits)))))
> > >     digits))
> > > 
> > > 
> > > ;; Recursion.
> > > (let go ((divisor 1) (candidates (list (list 0 (iota 10)))))
> > >   (if (> divisor 10)
> > >     (caar candidates)
> > >     (go (+ divisor 1)
> > >         (append-map
> > >           (lambda (x) (apply next divisor x))
> > >           candidates))))
> > > 
> > > 3816547290
> > 
> > Ruby:
> > 
> > def next_digit( divisor, digits_so_far )
> >   number_so_far = digits_so_far.join.to_i * 10
> >   ((0..9).to_a - digits_so_far).select{|d|
> >     ((number_so_far + d).modulo divisor).zero? }.
> >     map{|d| digits_so_far + [d]}
> > end
> > 
> > candidates = [[]]
> > 1.upto(10){|divisor|
> >   candidates = candidates.map{|digit_list|
> >     next_digit( divisor, digit_list) }.flatten(1) }
> > candidates
> > 
> >  ===>
> > [[3, 8, 1, 6, 5, 4, 7, 2, 9, 0]]
> 
> No one has yet posted a Forth solution.  Perhaps this Ruby version
> will be more understandable than the previous one.
> 
> def divisible( n, divisor )
>   n.modulo(divisor).zero?
> end
> 
> def one_more_digit( divisor, digits_so_far )
>   digits_avail = (0 .. 9).to_a - digits_so_far
>   base_for_new_number = digits_so_far.join.to_i * 10
>   digits_avail.select{ |d| divisible( base_for_new_number + d, divisor )}.
>     map{|d| digits_so_far + [d] }
> end
> 
> 
> Here's an example of how this function works:
> 
> one_more_digit( 4, [3, 8, 1] )
>     ==>[[3, 8, 1, 2], [3, 8, 1, 6]]
> 
> 
> 
> candidates = [[]]
> 1.upto(10){|divisor|
>   candidates = candidates.map{|digit_list|
>     one_more_digit( divisor, digit_list) }.flatten(1) }
> candidates
> 
> [[3, 8, 1, 6, 5, 4, 7, 2, 9, 0]]
> 
> Here's an example of how the "flatten" command works in Ruby:
> 
> [[[3, 8, 1, 2], [3, 8, 1, 6]]].flatten
>     ==>[3, 8, 1, 2, 3, 8, 1, 6]
> [[[3, 8, 1, 2], [3, 8, 1, 6]]].flatten(1)
>     ==>[[3, 8, 1, 2], [3, 8, 1, 6]]

Ocaml:

(* Using Int64 so that this will work on 32-bit systems. *)
let divisible digit_list divisor =
  let bignum =
    digit_list
    |> List.map string_of_int
    |> String.concat ""
    |> Int64.of_string
  and bigdivisor = Int64.of_int divisor in
  0L = Int64.rem bignum bigdivisor ;;

let one_more_digit divisor digits_so_far =
  [0;1;2;3;4;5;6;7;8;9]
  |> List.filter (fun d -> not (List.mem d digits_so_far))
  |> List.map (fun d -> digits_so_far @ [d])
  |> List.filter (fun dlist -> divisible dlist divisor) ;;

let rec  loop candidates = function
  | 11      -> candidates
  | divisor ->
      loop (candidates
             |> List.map (fun dlist -> one_more_digit divisor dlist)
             |> List.flatten)
           (divisor + 1)
in loop [[]] 1 ;;

[[3; 8; 1; 6; 5; 4; 7; 2; 9; 0]]

-- 
As more and more power gravitates in the capital, the more vital it becomes for
the corporate America to secure its interests by corrupting that seat of power.
www.kolumbus.fi/aquilon/america-middle-class-and-the-end-of-growth.htm

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.forth

csiph-web