calendar functions

calendar.go

func isLeap(y int) bool {
	if y%4 == 0 {
		if y%100 == 0 {
			return y%400 == 0
		}
		return true
	}
	return false
}


func daysInMonth(m, y int) int {
	if m == 1 {
		if isLeap(y) {
			return 29
		}
		return 28
	}
	if m == 0 || m == 2 || m == 4 || m == 6 || m == 7 || m == 9 || m == 11 {
		return 31
	}
	return 30
}

/*
strategy:

evaluate single years until we find a leap year

then evaluate in chunks of 4 years as a time in a simple, optimized loop with no branches
we don't need branches because there are only 14 year types, based only on the start day of the year and whether it's a leap year
furthermore, we know there is only one leap year per four years

straggler years are handled at the end */

func CountSundaysPipelinedPrecalced() int {


	// there are only 14 year configurations

	// number of months that start with sunday for each year configuration
	// year configuration = starting day of year + whether it's a leap year or not
	var sundaysPerCommonYear [7]int = [...]int{2, 2, 2, 1, 3, 1, 1}
	var sundaysPerLeapYear [7]int = [...]int{3, 2, 1, 2, 2, 1, 1}

	//var modSevenTable [12]int = [...]int{0,1,2,3,4,5,6,0,1,2,3,4}
	var modSevenTable [18]int = [...]int{0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3}
	
	var dayOfWeek int = 2
	var year int = 1901
	var sundaysCount int = 0

	// count non leap years until a leap year
	// once we find it, break out of this loop and move onto the branchless, optimized loop
	for ; year <= 2000; year++ {
		if isLeap(year) {
			break
		} else {
			sundaysCount += sundaysPerCommonYear[dayOfWeek]
			dayOfWeek = modSevenTable[dayOfWeek+1]
		}
	}

	// calculate days of the week for all four years we process
	dayOfWeekYear0 := dayOfWeek
	dayOfWeekYear1 := modSevenTable[dayOfWeekYear0+2]
	dayOfWeekYear2 := modSevenTable[dayOfWeekYear0+3]
	dayOfWeekYear3 := modSevenTable[dayOfWeekYear0+4]

	
	var iterations = (2000 - year)>>3
	
	
	// calculate 4 years at a time with no branches
	// each iteration, also calculate the next days of weeks for each 4 years we're processing
	// since we have all four values at the ready, and a table to skip four years, there is no dependency between these lookups
	// and they can all be done in parallel by the cpu
	
	// update: unrolled it one more time to handle 8 years at once,
	// this improved the function from 55ns to 44ns

	// testing against >=0 seems a little faster than >0
	for i := iterations-1 ; i >= 0; i-- {
		
		leapCount := sundaysPerLeapYear[dayOfWeekYear0]
		dayOfWeekYear0 = modSevenTable[dayOfWeekYear0+5]

		
		nonLeapCount1 := sundaysPerCommonYear[dayOfWeekYear1]
		dayOfWeekYear1 = modSevenTable[dayOfWeekYear1+5]

		
		nonLeapCount2 := sundaysPerCommonYear[dayOfWeekYear2]
		dayOfWeekYear2 = modSevenTable[dayOfWeekYear2+5]

		
		nonLeapCount3 := sundaysPerCommonYear[dayOfWeekYear3]
		dayOfWeekYear3 = modSevenTable[dayOfWeekYear3+5]

		sundaysCount += (leapCount + nonLeapCount1 + nonLeapCount2 + nonLeapCount3) 

		// calculate the next 8 years
		leapCount = sundaysPerLeapYear[dayOfWeekYear0]
		dayOfWeekYear0 = modSevenTable[dayOfWeekYear0+5]

		
		nonLeapCount1 = sundaysPerCommonYear[dayOfWeekYear1]
		dayOfWeekYear1 = modSevenTable[dayOfWeekYear1+5]

		
		nonLeapCount2 = sundaysPerCommonYear[dayOfWeekYear2]
		dayOfWeekYear2 = modSevenTable[dayOfWeekYear2+5]

		
		nonLeapCount3 = sundaysPerCommonYear[dayOfWeekYear3]
		dayOfWeekYear3 = modSevenTable[dayOfWeekYear3+5]
		

		sundaysCount += (leapCount + nonLeapCount1 + nonLeapCount2 + nonLeapCount3) 
			
		year += 8
	}


	// exact same as the first loop
	// handle any remaining years
	dayOfWeek = dayOfWeekYear0
	for ; year <= 2000; year++ {
		if isLeap(year) {
			sundaysCount += sundaysPerLeapYear[dayOfWeek]
			dayOfWeek = modSevenTable[dayOfWeek+2]
		} else {
			sundaysCount += sundaysPerCommonYear[dayOfWeek]
			dayOfWeek = modSevenTable[dayOfWeek+1]
		}
	}

	return sundaysCount
}





func evaluateYear(curDayOfWeek int, curSundaysCount int, startMonth int, endMonth int, y int) (int, int) {
	//leap := isLeap(y)
	
	for m := startMonth ; m <= endMonth ; m++ {
		
		if curDayOfWeek % 7 == 0 {
			curSundaysCount++
		}
		curDayOfWeek = (curDayOfWeek + daysInMonth(m, y)) % 7
	}
	return curSundaysCount, curDayOfWeek
}


/* doesn't quite work, something is probably off by one somewhere */

/* strategy: 
  evaluate single years until we find a year divisible by 400,
  then evaluate in chunks of 400 years 
  
  sunday counts for each 7 possible 400 year chunks are calculated at the beginning.
  
  handle straggler years at the end
  
  could be optimized further like the above solution, probably
*/
func CountSundaysGeneral400YearOpt(
	startYear int, startMonth int, startDay int, startDayOfWeek int,
	endYear int, endMonth int, endDay int) int {
	
	curDayOfWeek := startDayOfWeek

	var modSevenTable [12]int = [...]int{0,1,2,3,4,5,6,0,1,2,3,4}

	// calculate lookup tables for individual years
	// just 14 of these
	sundaysPerCommonYear, sundaysPerLeapYear := generateSingleYearTables()



	// there are only 7 types of 400 year chunks that start on a year divisible by 400
	// since they always start on a leap year 

	// calculate lookup tables for each possible 400 year chunk
	var fourHundredYearCounts [7]int = [...]int{0,0,0,0,0,0,0}
	var fourHundredYearNextDays [7]int = [...]int{0,0,0,0,0,0,0}
	for i := 0 ; i < 7 ; i++ {
		cnt := 0
		baseDayOfWeek := i
		for y := 0 ; y < 400 ; y++ {
			if isLeap(y) {
				cnt += sundaysPerLeapYear[baseDayOfWeek]
				baseDayOfWeek = modSevenTable[baseDayOfWeek+2]
			} else {
				cnt += sundaysPerCommonYear[baseDayOfWeek]
				baseDayOfWeek = modSevenTable[baseDayOfWeek+1]
			}
		}
		fourHundredYearCounts[i] = cnt
		fourHundredYearNextDays[i] = baseDayOfWeek
		
	}


	// if the start year+month, and end year+month are the same 
	if startYear == endYear && startMonth == endMonth {
		// handle this one weird edge case
		if startDay == 0 && startDayOfWeek == 0 {
			return 1
		} else {
			return 0
		}
					
	}
	
	// skip days until we reach the beginning of the month
	if startDay != 0 {
		daysInStartMonth := daysInMonth(startMonth, startYear)

		// days left in the month
		daysLeftInMonth := daysInStartMonth - startDay
		// skip N days, and get the day of the week for the next month
		curDayOfWeek = (curDayOfWeek + daysLeftInMonth) % 7
		
	}


	sundaysCount := 0


	// if it's less than a year
	// just run through months for this one year
	if startYear == endYear {
		
		sundaysCount, _ = evaluateYear(curDayOfWeek, sundaysCount, startMonth, endMonth, startYear)
		return sundaysCount
	}

	
	// run through remainder of first year
	sundaysCount, curDayOfWeek = evaluateYear(curDayOfWeek, sundaysCount, startMonth, 11, startYear)

	var yearsToEvaluate int = endYear-(startYear+1)


	if yearsToEvaluate > 800 {
	//if false { 
		// evaluate single years until we find a divisible by 400 leap year
		chunkStartYear := startYear+1
		for ; chunkStartYear % 400 != 0; chunkStartYear++ {
			if chunkStartYear % 4 == 0 {
				sundaysCount += sundaysPerLeapYear[curDayOfWeek]
				curDayOfWeek = modSevenTable[curDayOfWeek+2]
			} else {
				sundaysCount += sundaysPerCommonYear[curDayOfWeek]
				curDayOfWeek = modSevenTable[curDayOfWeek+1]
				
			}
		}

		// now we've found a 400 year chunk
		// evaluate as many of these chunks as possible


		var chunksToEvaluate int = yearsToEvaluate/400

		
		for i := 0 ; i < chunksToEvaluate ; i++ {
			sundaysCount += fourHundredYearCounts[curDayOfWeek]
			curDayOfWeek = fourHundredYearNextDays[curDayOfWeek]
		}
				
		yearsSkipped := (chunksToEvaluate * 400)
                

		// evaluate single years until the last year
		for y := chunkStartYear + yearsSkipped; y < endYear; y++ {
			if isLeap(y) {
				sundaysCount += sundaysPerLeapYear[curDayOfWeek]
				curDayOfWeek = modSevenTable[curDayOfWeek+2]
			} else {
				sundaysCount += sundaysPerCommonYear[curDayOfWeek]
				curDayOfWeek = modSevenTable[curDayOfWeek+1]
				
			}
		}
		
	} else {
		// evaluate single years until the last year
		for y := startYear+1; y < endYear; y++ {
			if isLeap(y) {
				sundaysCount += sundaysPerLeapYear[curDayOfWeek]
				curDayOfWeek = modSevenTable[curDayOfWeek+2]
			} else {
				sundaysCount += sundaysPerCommonYear[curDayOfWeek]
				curDayOfWeek = modSevenTable[curDayOfWeek+1]
				
			}
		}
	}

	// run through months for the last year
	sundaysCount, _ = evaluateYear(curDayOfWeek, sundaysCount, 0, endMonth, endYear)
	
		
	return sundaysCount
}