A sieve - a reversed sieve and a question

[RobbeK]

Hi all,

Driven by some remorse :-) (the extreme benchmark testings) .. attached two scripts I hope prove the good speed of TB.

- the first is the classic Eratosthenes prime sieve, but I did not use the inbuilt IsPrime, just the classic sieve. As an extra it also generates the twin primes. (still not proven their number (the twins) is infinite or not - like the Goldbach and Riemann hypothesis , in case you can prove it , you will rewarded with a lot of money - since 2000 , 1.000.000 $ for the Riemann ).

- got the idea to reverse the sieve, as there is no formula generating all primes between a bottom and upper limit - we can generate non-primes , as all not non-primes are primes this system works. As an extra the graphic presentation showing the frequency defined by N=axb (a,b >= 2) (green). (What speeds up the most in these two scripts is the fact 0xN=0 and axb=bxa -- such simple things can speed up the runtime several times)

-the question : Does TB always use strict evaluation ?? ... It could/would be very handy in cases like : a and b and c .... if it bails out after any false condition. (I need it to test several conditions at once of which one of them is critical in a way that if the script continues interpreting the rest of the line will generate an error (because out of the limits of an array) )

thanks in advance
Rob

[Petr Schreiber]

Thanks for posting this example,

I like the version with chart, looks cool!

I created commented derivation of the second example, to show some special thinBasic tricks. All such a places are commented with '[!]:


'------------------------------------------------------------------------------
' Project: Primes - reversed sieve
' File: Eratosthenes_Rev2
' Created: On 10-05-2013 at 10:51:34
'------------------------------------------------------------------------------

'[!] It is possible to define modules on single line
Uses "UI", "TBGL"

'[!] Variables declared in global space are global
String s
Integer probe(1000) , width , height
Integer i , j , k , l

'---Controls IDs---
Begin ControlID
%IDC_BUTTON_1
%IDC_EDIT_1
%IDC_CANVASLABEL
End ControlID

'------------------------------------------------------------------------------
' Main thinBasic function
'------------------------------------------------------------------------------
Function TBMain() As Long

MainWindow_Create(%HWND_DESKTOP)

End Function

'------------------------------------------------------------------------------
' Create main Window
'------------------------------------------------------------------------------
Function MainWindow_Create(ByVal hParent As Long) As Long

'[!] Variables declared in local scope are local by default
Long hDlg, hFont, lStyle, lStyleEx

'[!] No need for underscore for line continuation in most cases,
' thanks to so called "implicit line continuation"
lStyle = %WS_POPUP |
%WS_VISIBLE |
%WS_CAPTION |
%WS_SYSMENU |
%WS_MINIMIZEBOX

lStyleEx = 0

Dialog New Pixels, hParent, "Primes reversed sieve ", 10, 10, 1200, 300, lStyle, lStyleEx, To hDlg

' -- Fonts
hFont = Font_Create("MS Sans Serif", 8)
Dialog Send hDlg, %WM_SETFONT, hFont, 0

' -- Controls
'[!] Label can be used for TBGL "hijacking"
Control Add Label, hDlg, %IDC_CANVASLABEL, "", 190, 5, 1004, 285, %SS_SUNKEN
Control Add Button, hDlg, %IDC_BUTTON_1, "Start calculation", 5, 5, 180, 30, %WS_CHILD Or %WS_CLIPSIBLINGS Or %WS_TABSTOP Or %WS_VISIBLE Or %BS_PUSHBUTTON, 0
Control Add Textbox, hDlg, %IDC_EDIT_1, "", 5, 40, 180, 250, %WS_BORDER Or %WS_CHILD Or %WS_CLIPSIBLINGS Or %WS_TABSTOP Or %WS_VISIBLE Or %WS_VSCROLL Or %ES_AUTOVSCROLL Or %ES_MULTILINE, %WS_EX_CLIENTEDGE

' -- Callback link
Dialog Show Modal hDlg, Call MainWindow_Proc

' -- Releasing font
Win_DeleteObject hFont

End Function

'------------------------------------------------------------------------------
' Main WIndow CallBack handler
'------------------------------------------------------------------------------
CallBack Function MainWindow_Proc() As Long

Select Case (Callback_Message)

Case %WM_INITDIALOG
' -- Initialize display
initTBdisplay(Callback_Handle, %IDC_CANVASLABEL)

Case %WM_COMMAND
If %IDC_BUTTON_1 Then
If Callback_Control_Message = %BN_CLICKED Then

For k=2 To 500
For j=2 To 1000/k

Incr probe(k*j)

Next
If Not(Mod(k,25)) Then TBdisplay()
Next
updatebox()
Control Set Text Callback_Handle, %IDC_EDIT_1 , s
End If
EndIf


Select Case LOWRD(CBWPARAM)
Case %IDOK
Case %IDCANCEL
End Select

Case %WM_PAINT
k = 0
TBdisplay()

End Select

End Function

Function initTBDisplay( hDlg As DWord, hostControl As Long )
DWord hCtrl

'[!] Hijacking label for TBGL rendering
Control Handle hDlg, hostControl To hCtrl
TBGL_BindCanvas(hCtrl)

Control Get Client hDlg, hostControl To width, height


TBGL_DepthFunc(%TBGL_ALWAYS)
Dim hFont As DWord = TBGL_FontHandle("Courier New", 12)
TBGL_BuildFont( hFont )

End Function

Function TBDisplay()

TBGL_RenderMatrix2D (0,height,width,0)

TBGL_ClearFrame

TBGL_PrintFont(Format$(k)+"/500", 10, 20)
For i=3 To 1000
If probe(i) Then
TBGL_Color(0,200,100)
TBGL_Line (i,200-4*probe(i),i,200)
Else
TBGL_Color (200,0,0)
TBGL_Line (i,200,i,203)
EndIf
Next

TBGL_DrawFrame
End Function

Sub updatebox()
Integer x

s = "Primes " + $CRLF '[!] CRLF is built in equate for 13,10;
' you can also use multiple PARAMETERS like Chr$(13, 10),
' instead of two Chr$ calls

For x=2 To 997
If probe(x)=0 Then
s += Format$(x) + " " '[!] It is possible to use += for fast concatenation of strings
EndIf
Next

'[!] Alternative
' For x=2 To 997
' If IsPrime(x) Then
' s += Format$(x) + " "
' EndIf
' Next


'[!] Fill all elements with zero
Array Fill probe With 0

End Sub



Petr

[RobbeK]

Thanks for the tricks and tips, Petr , much appreciated.
(why you call it hijacking ? ).
Ah, yes, TB never does lazy evaluation then ?

best
Rob

[Petr Schreiber]

I call it hijacking, because it is some kind of mis-using the poor label. It looses its identity and is commanded by evil TBGL :)

Regarding lazy evaluation - I am not sure, Eros will know better.


Petr