OpenCL implementation to check the sigma_odd problem, mostly like the other implementations but without the advantage of the shortcut in the factorization. If your GPU supports not too old OpenCL version, use the specific function ctz into divide_until_odd() instead the manual computation. Some tips used: "optimizing specifically for Processor Graphics OpenCL* device, ensure all conditionals are evaluated outside of code branches" https://software.intel.com/sites/landingpage/opencl/optimization-guide/Notes_on_Branching_Loops.htm. More...

Typedefs
typedef unsigned long	nat_type
	Type for natural number used in all code, on 64 bits. More...

typedef unsigned int	prime_type
	Type for prime number, particularly for the table of primes. More...

Functions
nat_type	ceil_eighth_root (nat_type n)
	Return the eighth root of n rounded to above. More...

nat_type	divide_until_odd (nat_type n)
	Return n divided by 2 until the result is odd. More...

nat_type	floor_eighth_root (nat_type n)
	Return the eighth root of n rounded to below. More...

nat_type	floor_square_root (nat_type n)
	Return the square root of n rounded to below. More...

bool	is_divide (nat_type d, nat_type n)
	Return true iff d divide n, i.e. if n is divisible by d. More...

bool	is_even (nat_type n)
	Return true iff n is even. More...

bool	is_in_table (__global const nat_type begin, __global const nat_type end, const nat_type n)
	Return true iff n is in the table. More...

bool	is_odd (nat_type n)
	Return true iff n is odd. More...

bool	is_varsigma_odd_lower (__global const prime_type *primes, nat_type n)
	Return true iff varsigma_odd(n) < n. More...

bool	is_varsigma_odd_lower__optimized (__global const prime_type *primes, nat_type n)
	Version of is_varsigma_odd_lower() rewritten to OpenCL. More...

bool	is_varsigma_odd_lower__simplified (__global const prime_type *primes, nat_type n)
	Simplified version of is_varsigma_odd_lower(). More...

nat_type	pow_nat (nat_type n, unsigned int k)
	Return x^k, x power k. More...

nat_type	square (nat_type n)
	Return n*n. More...

nat_type	sum_geometric_progression_strict (nat_type r, unsigned int k)
	Return the sum of the (k + 1) terms of the geometric progression of the common ratio r. More...

nat_type	sigma_odd_upper_bound (nat_type n)
	Return an upper bound of sigma_odd(n). More...

nat_type	upper_square_root (nat_type n)
	Return an approximation of the square root of n. The results is always >= the exact square root. More...

nat_type	varsigma_odd (__global const prime_type *primes, nat_type n)
	Return varsigma_odd(n), i.e. the sum of all odd divisors of n, divided by 2 until to be odd. More...

__kernel void	check_ns (__global const prime_type primes, __global const nat_type ns, unsigned int nb, __global unsigned char *results)

__kernel void	check_ns__optimized (__global const prime_type primes, __global const nat_type ns, unsigned int nb, __global unsigned char *results)

__kernel void	check_ns__simplified (__global const prime_type primes, __global const nat_type ns, unsigned int nb, __global unsigned char *results)

__kernel void	compute_partial_sigma_odd (__global const prime_type primes, unsigned int prime_offset, unsigned int opencl_nb, nat_type n, __global nat_type factors)

__kernel void	test__divide_until_odd (__global const prime_type primes, __global const nat_type ns, __global nat_type *results)

__kernel void	test__floor_square_root (__global const prime_type primes, __global const nat_type ns, __global nat_type *results)

__kernel void	test__pow_nat (__global const prime_type primes, __global const nat_type ns, __global nat_type *results)

__kernel void	test__sum_geometric_progression_strict (__global const prime_type primes, __global const nat_type ns, __global nat_type *results)

__kernel void	test__varsigma_odd (__global const prime_type primes, __global const nat_type ns, __global nat_type *results)

Detailed Description

OpenCL implementation to check the sigma_odd problem, mostly like the other implementations but without the advantage of the shortcut in the factorization. If your GPU supports not too old OpenCL version, use the specific function ctz into divide_until_odd() instead the manual computation. Some tips used: "optimizing specifically for Processor Graphics OpenCL* device, ensure all conditionals are evaluated outside of code branches" https://software.intel.com/sites/landingpage/opencl/optimization-guide/Notes_on_Branching_Loops.htm.

Definition in file sigmaodd.cl.

Typedef Documentation

◆ nat_type

typedef unsigned long nat_type

Type for natural number used in all code, on 64 bits.

Definition at line 22 of file sigmaodd.cl.

◆ prime_type

typedef unsigned int prime_type

Type for prime number, particularly for the table of primes.

Definition at line 28 of file sigmaodd.cl.

Function Documentation

◆ ceil_eighth_root()

nat_type ceil_eighth_root ( nat_type n )

Return the eighth root of n rounded to above.

Definition at line 208 of file sigmaodd.cl.

◆ check_ns()

__kernel void check_ns	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		unsigned int	nb,
		__global unsigned char *	results
	)

Definition at line 534 of file sigmaodd.cl.

◆ check_ns__optimized()

__kernel void check_ns__optimized	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		unsigned int	nb,
		__global unsigned char *	results
	)

Definition at line 549 of file sigmaodd.cl.

◆ check_ns__simplified()

__kernel void check_ns__simplified	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		unsigned int	nb,
		__global unsigned char *	results
	)

Definition at line 563 of file sigmaodd.cl.

◆ compute_partial_sigma_odd()

__kernel void compute_partial_sigma_odd	(	__global const prime_type *	primes,
		unsigned int	prime_offset,
		unsigned int	opencl_nb,
		nat_type	n,
		__global nat_type *	factors
	)

Definition at line 578 of file sigmaodd.cl.

◆ divide_until_odd()

nat_type divide_until_odd ( nat_type n )

Return n divided by 2 until the result is odd.

Parameters

n != 0

Definition at line 218 of file sigmaodd.cl.

◆ floor_eighth_root()

nat_type floor_eighth_root ( nat_type n )

Return the eighth root of n rounded to below.

Definition at line 235 of file sigmaodd.cl.

◆ floor_square_root()

nat_type floor_square_root ( nat_type n )

Return the square root of n rounded to below.

Definition at line 256 of file sigmaodd.cl.

◆ is_divide()

bool is_divide	(	nat_type	d,
		nat_type	n
	)

Return true iff d divide n, i.e. if n is divisible by d.

Parameters

d	!= 0
n

Definition at line 277 of file sigmaodd.cl.

◆ is_even()

bool is_even ( nat_type n )

Return true iff n is even.

Definition at line 283 of file sigmaodd.cl.

◆ is_in_table()

bool is_in_table	(	__global const nat_type *	begin,
		__global const nat_type *	end,
		const nat_type	n
	)

Return true iff n is in the table.

Definition at line 289 of file sigmaodd.cl.

◆ is_odd()

bool is_odd ( nat_type n )

Return true iff n is odd.

Definition at line 316 of file sigmaodd.cl.

◆ is_varsigma_odd_lower()

bool is_varsigma_odd_lower	(	__global const prime_type *	primes,
		nat_type	n
	)

Return true iff varsigma_odd(n) < n.

If there is no enough primes then return false.

"Same" implementation than sequential/threads/MPI.

Parameters

primes
n	odd >= 3

Definition at line 322 of file sigmaodd.cl.

◆ is_varsigma_odd_lower__optimized()

bool is_varsigma_odd_lower__optimized	(	__global const prime_type *	primes,
		nat_type	n
	)

Version of is_varsigma_odd_lower() rewritten to OpenCL.

Parameters

primes
n	odd >= 3

Definition at line 361 of file sigmaodd.cl.

◆ is_varsigma_odd_lower__simplified()

bool is_varsigma_odd_lower__simplified	(	__global const prime_type *	primes,
		nat_type	n
	)

Simplified version of is_varsigma_odd_lower().

Parameters

primes
n	odd >= 3

Definition at line 407 of file sigmaodd.cl.

◆ pow_nat()

nat_type pow_nat	(	nat_type	n,
		unsigned int	k
	)

Return x^k, x power k.

Definition at line 439 of file sigmaodd.cl.

◆ sigma_odd_upper_bound()

nat_type sigma_odd_upper_bound ( nat_type n )

Return an upper bound of sigma_odd(n).

If n == 1 then return 1, else return floor((n * ceil(2 * (n - 1)^{1/8} + 1)) / 2).

Parameters

n odd

Definition at line 474 of file sigmaodd.cl.

◆ square()

nat_type square ( nat_type n )

Return n*n.

Definition at line 458 of file sigmaodd.cl.

◆ sum_geometric_progression_strict()

nat_type sum_geometric_progression_strict	(	nat_type	r,
		unsigned int	k
	)

Return the sum of the (k + 1) terms of the geometric progression of the common ratio r.

If r is prime then the result is equal to the sum of the divisors of r.

In fact calculates (r^k - 1) / (r - 1) + r^k to avoid some overflow.

Parameters

r	> 1
k

Returns: 1 + r + r^2 + r^3 + ... + r^k = (r^(k + 1) - 1) / (r - 1)

Definition at line 464 of file sigmaodd.cl.

◆ test__divide_until_odd()

__kernel void test__divide_until_odd	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		__global nat_type *	results
	)

Definition at line 658 of file sigmaodd.cl.

◆ test__floor_square_root()

__kernel void test__floor_square_root	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		__global nat_type *	results
	)

Definition at line 668 of file sigmaodd.cl.

◆ test__pow_nat()

__kernel void test__pow_nat	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		__global nat_type *	results
	)

Definition at line 678 of file sigmaodd.cl.

◆ test__sum_geometric_progression_strict()

__kernel void test__sum_geometric_progression_strict	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		__global nat_type *	results
	)

Definition at line 688 of file sigmaodd.cl.

◆ test__varsigma_odd()

__kernel void test__varsigma_odd	(	__global const prime_type *	primes,
		__global const nat_type *	ns,
		__global nat_type *	results
	)

Definition at line 698 of file sigmaodd.cl.

◆ upper_square_root()

nat_type upper_square_root ( nat_type n )

Return an approximation of the square root of n. The results is always >= the exact square root.

Definition at line 482 of file sigmaodd.cl.

◆ varsigma_odd()

nat_type varsigma_odd	(	__global const prime_type *	primes,
		nat_type	n
	)

Return varsigma_odd(n), i.e. the sum of all odd divisors of n, divided by 2 until to be odd.

If there is no enough primes then return 0.

Parameters

primes
n	odd >= 3

Definition at line 497 of file sigmaodd.cl.

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ nat_type

◆ prime_type

Function Documentation

◆ ceil_eighth_root()

◆ check_ns()

◆ check_ns__optimized()

◆ check_ns__simplified()

◆ compute_partial_sigma_odd()

◆ divide_until_odd()

◆ floor_eighth_root()

◆ floor_square_root()

◆ is_divide()

◆ is_even()

◆ is_in_table()

◆ is_odd()

◆ is_varsigma_odd_lower()

◆ is_varsigma_odd_lower__optimized()

◆ is_varsigma_odd_lower__simplified()

◆ pow_nat()

◆ sigma_odd_upper_bound()

◆ square()

◆ sum_geometric_progression_strict()

◆ test__divide_until_odd()

◆ test__floor_square_root()

◆ test__pow_nat()

◆ test__sum_geometric_progression_strict()

◆ test__varsigma_odd()

◆ upper_square_root()

◆ varsigma_odd()