5
$\begingroup$

Suppose I want to compute $f(1)\vee f(2) \vee \ldots \vee f(10^{10})$, but I know a priori that $f(n)$ is True for some $n \ll 10^{10}$ with high probability. For example, f = PrimeQ.

One way to do this is to write: Or[f/@Range[1,10^10]], but that would involve allocating memory for $10^{10}$ elements, as well as computing f unnecessarily. (I overcame the latter problem with using Hold, but the memory problem still stands).

Question: Is there a way to compute Or[f[1], ..., f[10^10]] without allocating memory for $10^{10}$ booleans?

I've done some research: it seems like Functional style using lazy lists? might work, but I'm wondering if there is a shorter solution -- one that does not involve defining streams?

$\endgroup$
3
  • 2
    $\begingroup$ Maybe I missing something but if you know that f[n] is True for n<<10^10 isn't then Or automatically True? Even if you do not know if it is so then one occurance is enough: Do[If[PrimeQ@i, Print[i]; Break[];], {i, 10^10}] $\endgroup$
    – Kuba
    Commented Jul 22, 2013 at 21:50
  • $\begingroup$ Ah, sorry I should have been more clear. I meant that there is a high probability that f[n] is True for some n << 10^10. But yes, a Do loop seems like what I need. I still wonder though, if there is a more functional way of approaching this problem. $\endgroup$
    – Kevin
    Commented Jul 22, 2013 at 22:11
  • $\begingroup$ I am closing this question as a duplicate. If you feel that your question is not addressed there please clarify for me how it is different and I shall reopen this. $\endgroup$
    – Mr.Wizard
    Commented Jul 23, 2013 at 3:39

2 Answers 2

5
$\begingroup$

Streams and iterators

Using streams would certainly be one of the most elegant ways to do this. In any case, you will at least need an iterator for your sequence of numbers. The reason why an abstraction of an iterator is useful is because it separates the iteration over your sequence from the stuff you want to do with individual elements, so that you can implement them independently. It also inverses the control, since rather than doing an active iteration with your sequence, you get a next number on demand. This leads to a more modular code and better abstractions.

Iterator for a sequence of numbers

Here is one possibility. First, define an iterator for equidistant numbers:

ClearAll[makeIterator];
makeIterator[min_,max_,step_]:=
    Module[{current=min},            
        With[{curr=current},
            current=If[current+step<=max,current+step,Null];curr
        ]&
    ];

it can be used as

iter = makeIterator[1, 10, 1];
iter[]
iter[]
iter[]

(*
  1
  2
  3
*)

Implementation of Or

Now, here is a possible implementation of Or:

ClearAll[lazyOr];
lazyOr[iter_,f_]:=
    While[            
        True,
        (If[#1=!=Null,If[f[#1],Return[True]],Return[False]]&)[
            iter[]
        ]
    ]

and here is how we can use it:

lazyOr[makeIterator[1, 10, 1], # > 10 &]

(* False *)

lazyOr[makeIterator[1, 10, 1], # > 9 &]

(* True  *)

lazyOr[makeIterator[1, 10^10, 1], PrimeQ] // AbsoluteTiming

(*  {0.000977, True}  *)

Again, I want to stress that this is just a light-weight version of the lazy streams, where we had to make Or less trivial because it should do the iteration. The full lazy stream construction postpones iteration until we actually request an element, and is more elegant in that sense.

$\endgroup$
4
  • $\begingroup$ Is an analog possible when I am interested in the set of values {f(a) : a in A} for some arbitrary finite set A, not just when A = {1, ... ,n} for some n? EDIT: It seems all I need to do is to generalize the makeIterator function, so that it takes in a set (list) and returns an iterator for that list. Is this possible? $\endgroup$
    – Kevin
    Commented Jul 22, 2013 at 22:17
  • $\begingroup$ @user12677 It is possible in cases when you can enumerate your set in some way - provide a next operator that would, when applied to a current element, produce the next element, for some specific ordering of your set. It should be such that repeated application of next would exhaust your set. So, if such an ordering and an operator exist (if you can construct them), then this will work. Of course, if you already have a list of elements, it will induce a natural ordering by position, but this is a special case. $\endgroup$ Commented Jul 22, 2013 at 22:21
  • $\begingroup$ @user12677 Well, if you have a list, then the generalization is rather trivial: makeIterator[lst_List] := With[{len = Length[lst]}, Module[{n = 1},Function[If[n <= len, lst[[n++]], Null]]]]. $\endgroup$ Commented Jul 22, 2013 at 22:25
  • $\begingroup$ @user12677 Was glad to help. Thanks for the accept. $\endgroup$ Commented Jul 22, 2013 at 23:55
1
$\begingroup$

It looks like you only need a looping construct that terminates when the first True is encountered with the Or operation. So how about this:

f = PrimeQ

(* ==> PrimeQ *)

notFound = False;
n = 0;
While[! notFound,
 n += 1;
 notFound = notFound || f[n]
 ]; n

(* ==> 2 *)
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.